This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |