#include <bits/stdc++.h>
using namespace std;
#define int int64_t
struct Segtree {
int n;
int nn;
vector<int> mn;
vector<int> mx;
vector<int> add;
Segtree(int sz,vector<int> &a) {
n=1;
nn=sz;
while (n<sz)n*=2;
mn.assign(2*n,1e17);
mx.assign(2*n,0);
add.assign(2*n,0);
build(a,0,0,n);
}
void build(vector<int> &a, int x, int lx, int rx) {
if (rx-lx==1) {
if (lx<(int)a.size()) {
mn[x]=mx[x]=a[lx];
}
return;
}
int m=(lx+rx)/2;
build(a,2*x+1,lx,m);
build(a,2*x+2,m,rx);
mx[x]=max(mx[2*x+1],mx[2*x+2]);
mn[x]=min(mn[2*x+1],mn[2*x+2]);
}
void pushdown(int x) {
if (add[x]==0)return;
mn[2*x+1]+=add[x];
mx[2*x+1]+=add[x];
mn[2*x+2]+=add[x];
mx[2*x+2]+=add[x];
add[2*x+1]+=add[x];
add[2*x+2]+=add[x];
add[x]=0;
}
void inc(int l, int r, int x, int lx, int rx) {
if (lx >= r || rx <= l) return;
if (rx-lx==1) {
mn[x]++;
mx[x]++;
return;
}
pushdown(x);
if (lx >= l && rx <= r) {
add[x]++;
mn[x]++;
mx[x]++;
return;
}
int m=(lx+rx)/2;
inc(l, r, 2*x+1, lx, m);
inc(l, r, 2*x+2, m, rx);
mx[x]=max(mx[2*x+1], mx[2*x+2]);
mn[x]=min(mn[2*x+1], mn[2*x+2]);
}
void inc(int l, int r) {
inc(l, r, 0, 0, n);
}
int first(int v, int x, int lx, int rx) {
if (rx-lx==1) {
if (mn[x] < v) return -1;
return lx;
}
pushdown(x);
int m = (lx+rx)/2;
if (mx[2*x+1] >= v) {
return first(v, 2*x+1, lx, m);
}
else {
return first(v, 2*x+2, m, rx);
}
}
int first(int v) {
return first(v, 0, 0, n);
}
int last(int v, int x, int lx, int rx) {
if (rx-lx==1) {
if (mn[x] > v) return -1;
return lx;
}
pushdown(x);
int m=(lx+rx)/2;
if (mn[2*x+2] <= v) return last(v, 2*x+2, m, rx);
else return last(v, 2*x+1, lx, m);
}
int last(int v) {
return last(v, 0, 0, n);
}
int getValue(int i, int x, int lx, int rx) {
if (rx-lx==1) {
return mn[x];
}
pushdown(x);
int m=(lx+rx)/2;
if (i<m)return getValue(i,2*x+1,lx,m);
else return getValue(i, 2*x+2,m,rx);
}
int getValue(int i) {
return getValue(i, 0, 0, n);
}
void query(int start, int numInc) {
int firstIndex = first(start);
if (firstIndex == -1 || firstIndex >= nn) return;
if (firstIndex + numInc - 1 >= nn - 1) {
inc(firstIndex, nn);
return;
}
int valueOfLast = getValue(firstIndex + numInc - 1);
int fRange = first(valueOfLast), eRange = last(valueOfLast);
// cout<<fRange<<" "<<eRange<<"\n";
int end = firstIndex + numInc - 1;
if (firstIndex < fRange) {
inc(firstIndex, fRange);
numInc -= (fRange - firstIndex);
}
inc(eRange - numInc + 1, eRange + 1);
}
void all() {
for (int i=0;i<nn;i++) {
cout<<getValue(i)<<" ";
}
cout<<"\n";
}
};
signed main() {
int n,q;cin>>n>>q;
vector<int> a(n);
for (int &x:a)cin>>x;
sort(a.begin(),a.end());
Segtree sg(n, a);
for (int i=0;i<q;i++) {
char d;cin>>d;
if (d == 'F') {
int c,h;cin>>c>>h;
sg.query(h,c);
}
else{
int mn,mx;cin>>mn>>mx;
int f=sg.first(mn);
if (f==-1 || f >= n){
cout<<0<<"\n";
continue;
}
int s=sg.last(mx);
if (s==-1)s=n-1;
cout<<s-f+1<<"\n";
}
// sg.all();
}
}
Compilation message
grow.cpp: In member function 'void Segtree::query(int64_t, int64_t)':
grow.cpp:153:13: warning: unused variable 'end' [-Wunused-variable]
153 | int end = firstIndex + numInc - 1;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
7504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
1176 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
158 ms |
1268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
120 ms |
4180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
7288 KB |
Output is correct |
| 2 |
Incorrect |
186 ms |
7252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
127 ms |
7256 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
208 ms |
7244 KB |
Output is correct |
| 2 |
Incorrect |
159 ms |
7332 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
7508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
7768 KB |
Output is correct |
