By cadmiumky, history, 2 weeks ago,

## 103423A - Bordered Subarrays

Idea and Solution: Gheal

Solution

Solution
Author's Note

## 103423C - Birthday Nim

Idea: Gheal

Solution: tibinyte and Gheal

Solution

• +30

 » 2 weeks ago, # |   +5 Auto comment: topic has been updated by cadmiumky (previous revision, new revision, compare).
 » 10 days ago, # |   +8 No code for B (yet!). But here's A and C: Problem A#include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; const int MOD = 1e9 + 7; template struct Seg { // comb(ID,b) = b const T ID = 0; T comb(T a, T b) { return a+b; } int n; vector seg; void init(int _n) { n = _n; seg.assign(2*n,ID); } void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); } void upd(int p, T val) { // set val at position p seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); } T query(int l, int r) { // sum on interval [l, r] T ra = ID, rb = ID; for (l += n, r += n+1; l < r; l /= 2, r /= 2) { if (l&1) ra = comb(ra,seg[l++]); if (r&1) rb = comb(seg[--r],rb); } return comb(ra,rb); } }; int st[20][(int)1e6 + 1]; inline int log2(int x) { return 31 - __builtin_clz(x); } int query (int l, int r) { if (l == r) { return st[0][l]; } const int i = log2(r - l + 1); return min(st[i][l], st[i][r + 1 - (1 << i)]); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; Seg segTree; segTree.init(n); vector v(n); for (int i = 0; i < n; i++) { cin >> v[i]; st[0][i] = v[i]; } for (int i = 1; i < 20; i++) { for (int j = 0; j + (1 << i) <= n; j++) { st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); } } vector vec = {}; long long ans = 0; for (int i = n - 1; i >= 0; i--) { if (vec.empty() || v[i] <= v[vec.back()]) { vec.push_back(i); segTree.upd(i, 1); } if (v[i] > v[vec.back()]) { while (!vec.empty() && v[i] > v[vec.back()]) { segTree.upd(vec.back(), 0); vec.pop_back(); } vec.push_back(i); segTree.upd(i, 1); } int l = i; int r = n - 1; while (l != r) { int m = (l + r)/2; if (query(i, m) < v[i]) { r = m; } else { l = m + 1; } } if (query(i, n - 1) >= v[i]) { l = n; } if (l == 0) { continue; } ans += segTree.query(0, l - 1); } cout << ans << '\n'; }  Problem C#include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; const int MOD = 1e9 + 7; long long binPow (long long x, long long y) { long long ans = 1; long long res = x; while (y > 0) { if (y & 1) { ans *= res; ans %= MOD; } res *= res; res %= MOD; y /= 2; } return ans; } long long inv (long long x) { return binPow(x, MOD - 2); } vector fact = {1}; ll combo (ll x, ll y) { if (y == 0) return 1; if (x < y) return 0; return (fact[x] * inv((fact[x - y] * fact[y]) % MOD)) % MOD; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, K; cin >> N >> K; long long ans = 1; vector arr(N); vector moves(K + 1); moves.assign(K + 1, 0); for (int i = 0; i < N; i++) { cin >> arr[i]; } while (fact.size() != (int)2e5 + 1) { fact.push_back((fact.size() * fact.back()) % MOD); } for (int k = 1; k <= K; k++) { moves[k] = 1; for (int i = 0; i < N; i++) { moves[k] *= combo(arr[i] + k - 1, k - 1); moves[k] %= MOD; } } long long delta = 0; for (int i = 0; i < moves.size() - 1; i++) { delta += (long long)pow(-1, i % 2) * (moves[i] * combo(K, i)) % MOD; delta += MOD; delta %= MOD; } cout << (moves.back() + delta) % MOD; } 
•  » » 9 days ago, # ^ | ← Rev. 2 →   0 (my) code for B My code#include #include #include using namespace std; namespace SegTree { int tree[800001]; int lazy[800001]; void updatenod(int node, int cl, int cr) { tree[node]=max(tree[node],lazy[node]); //cerr << "++" << lazy[node] <<' '<< cl <<' '<<(cl+cr>>1) <<' '<< cr << '\n'; if(cl!=cr) { lazy[node*2]=max(lazy[node*2],lazy[node]); lazy[node*2+1]=max(lazy[node*2+1],lazy[node]); } } void init() { for(int i=0; i<=800000; i++) tree[i]=0,lazy[i]=0; } void update(int l, int r, int val, int node=1, int cl=1, int cr=200000) { updatenod(node,cl,cr); if(l<=cl && cr<=r) { lazy[node]=val; //cerr << cl << ' '<< cr<<' '<< val << '\n'; return; } int mid=(cl+cr>>1); if(l<=mid) update(l,r,val,2*node,cl,mid); if(mid=limit; } int mid=cl+cr>>1; if(poz<=mid) return query(poz,limit,node*2,cl,mid); return query(poz,limit,node*2+1,mid+1,cr); } }; struct trip { int a,b,c; int type; bool operator <(const trip& x) const { return ((type<=0? b : a) == (x.type<=0? x.b : x.a)) ? type>x.type : ((type<=0? b : a) < (x.type<=0? x.b : x.a)); } }; vector segm; vector rez; int main() { /// i denoted -x the xth pass, and as +x, the (x-1)th blocker (this is what is kept in .type so i can reconsitute the vector rez, the results for each query) SegTree::init(); int n,k; trip temp; cin >> n >> k; rez.resize(n); for(int i=0; i> temp.a >>temp.b >> temp.c; temp.type=-i; temp.c-=temp.a; //cout << temp.a << ' '<< temp.b << ' '<< temp.c <<'\n'; segm.push_back(temp); } //cout << '\n'; temp.type=1; for(int i=0; i> temp.a >>temp.b >>temp.c; temp.b-=temp.a; temp.c-=temp.a; segm.push_back(temp); //cout << temp.a << ' '<< temp.b << ' '<< temp.c <<'\n'; } //cout << '\n'; sort(segm.begin(),segm.end()); for(auto x:segm) { //cout << x.a << ' '<< x.b << ' '<< x.c << ' '<< x.type << '\n'; if(x.type==1) { SegTree::update(x.b,x.c,x.a); } else { rez[-x.type]=SegTree::query(x.c,x.a); } } for(auto x:rez) cout << 1-x << '\n'; }