#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] == inf)
return;
if(isLeaf[k]){
t[k] = {min(t[k].mx, tag[k]), 1, 0, min(t[k].mx, tag[k])};
}
else if( tag[k] > t[k].secmx ){
t[k].s += 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]);
}
else if(tag[k] <= t[k].secmx){
tag[k << 1] = min(tag[k << 1], tag[k]);
tag[k << 1 | 1] = min(tag[k << 1 | 1], tag[k]);
refresh(k << 1);
refresh(k << 1 | 1);
t[k] = t[k<<1]+t[k<<1|1];
}
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)
return;
if( l == r){
tag[k]= val;
refresh(k);
return;
}
if(l >= beg && r <= en && val > t[k].secmx){
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);
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);
t[k] = t[k<<1]+t[k<<1|1];
}
void initialise(int n, int q, int h[]) {
N = n;
Q = q;
build(1,1,N, h);
/*cout << "Printing tree after building\n";
printTree(1,1,N);*/
}
void cut(int l, int r, int k) {
/*cout << "printing tree before query\n";
printTree(1,1,N);*/
while(k){
Node ret = getNodeQuery(1,1,N, l, r);
//cout << ret.mx << " " << ret.fmx << " " << ret.secmx << " from " << l << " " << r << " " << k << endl;
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);
return;
}
}
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 |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2083 ms |
37440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
