Submission #599244

#TimeUsernameProblemLanguageResultExecution timeMemory
599244CaroLindaWeirdtree (RMI21_weirdtree)C++14
100 / 100
584 ms40504 KiB
#include "weirdtree.h" #include <bits/stdc++.h> #define ll long long const int inf = 1e9+10; const int MAXN = 3e5+10; using namespace std; // ------ DECLARATIONS ------ int N, Q; struct Node{ int mx, fmx, secmx; ll s; } t[MAXN << 2]; int tag[MAXN << 2]; bool isLeaf[MAXN << 2]; // -------------------------- int m(int l, int r){ return (l+r)>>1; } Node operator + (Node A, Node B){ if(A.mx < B.mx) swap(A,B); if(A.mx > B.mx) return { A.mx, A.fmx, max(A.secmx, B.mx), A.s+B.s }; else return { A.mx, A.fmx+B.fmx, max(A.secmx, B.secmx), A.s+B.s }; } void refresh(int k){ if(tag[k] >= t[k].mx) return (void)(tag[k] = inf); if(isLeaf[k]){ t[k] = { tag[k], 1, 0, tag[k] }; return (void)(tag[k] = inf); } if(tag[k] > t[k].secmx){ t[k].s += (ll)t[k].fmx * (tag[k]-t[k].mx); t[k].mx = tag[k]; } tag[k<<1] = min(tag[k<<1], tag[k]); tag[k<<1|1] = min(tag[k<<1|1], tag[k]); tag[k] = inf; } void build(int k, int l, int r, int *h){ tag[k] = inf; if( l == r){ t[k] = { h[l], 1, 0, h[l] }; isLeaf[k] = true; return; } build(k << 1 , l , m(l,r) , h); build(k << 1 | 1, m(l,r)+1, r, h); t[k] = t[k<<1]+t[k<<1|1]; } Node getNodeQuery(int k, int l, int r, int beg, int en){ refresh(k); if(l >= beg && r <= en) return t[k]; if(en <= m(l,r)) return getNodeQuery(k<< 1 , l , m(l,r), beg, en ); else if( beg > m(l,r) ) return getNodeQuery(k << 1 |1 , m(l,r)+1, r, beg, en); return getNodeQuery(k << 1 , l , m(l,r), beg, en)+ getNodeQuery(k << 1|1,m(l,r)+1, r, beg, en); } void putTag(int k, int l, int r, int beg, int en, int val){ refresh(k); if( l > en || r < beg || l > r || val > t[k].mx) return; if((l >= beg && r <= en && val > t[k].secmx) || l == r){ tag[k] = val; refresh(k); return; } putTag(k << 1, l , m(l,r), beg, en, val); putTag(k << 1 | 1 , m(l,r)+1, r, beg, en, val); t[k] = t[k<<1]+t[k<<1|1]; } int getIndex(int k, int l, int r, int beg, int en, int toCompare, int &qtt){ refresh(k); if(t[k].mx < toCompare || l > en || r < beg) return 0; if(l >= beg && r <= en && t[k].fmx < qtt) return qtt -= t[k].fmx, 0; if( l == r ) return qtt--, l; int al = getIndex(k << 1 , l , m(l,r), beg, en, toCompare, qtt); if(al) return al; return getIndex(k << 1 | 1, m(l,r)+1, r, beg, en, toCompare, qtt); } void printTree(int k, int l, int r){ refresh(k); cout << l << " " << r << " -> " << t[k].mx << " " << t[k].fmx << " " << t[k].secmx << endl; if( l == r) return; printTree(k << 1, l , m(l,r)); printTree(k << 1 | 1, m(l,r)+1, r); } ll getAnswerQuery(int k, int l, int r, int beg, int en){ refresh(k); if(l > en || r < beg) return 0; if(l >= beg && r <= en) return t[k].s; ll al = getAnswerQuery(k << 1 , l , m(l,r), beg, en); ll ar = getAnswerQuery(k << 1 | 1, m(l,r)+1, r, beg, en); t[k] = t[k<<1]+t[k<<1|1]; return al+ar; } void modifyPoint(int k, int l, int r, int id, int newVal){ refresh(k); if(l == r) return (void)( t[k] = {newVal, 1, 0, newVal} ); if(id <= m(l,r)) modifyPoint(k<<1 , l , m(l,r), id, newVal); else modifyPoint(k << 1 | 1, m(l,r)+1, r, id, newVal); refresh(k<<1); refresh(k<<1|1); t[k] = t[k<<1]+t[k<<1|1]; //cout << l << " " << r << " " << t[k].mx << " " << t[k].secmx << " " << t[k].s << endl; } void initialise(int n, int q, int h[]) { N = n; Q = q; build(1,1,N, h); } void cut(int l, int r, int k) { while(k){ Node ret = getNodeQuery(1,1,N, l, r); if(!ret.mx) return; ll credits = ret.mx - ret.secmx; credits *= ret.fmx; if(credits <= k){ putTag(1,1,N, l, r ,ret.secmx); k -= credits; continue; } int m = k % ret.fmx; ll newVal = ret.mx - k/ret.fmx; int idx = m ? getIndex(1,1,N, l, r, ret.mx, m) : l-1; putTag(1,1,N, l,idx, newVal-1); putTag(1,1,N, idx+1, r, newVal); break; } } void magic(int i, int x) { modifyPoint(1,1,N, i, x); } long long int inspect(int l, int r) { return getAnswerQuery(1,1,N, l, r); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...