#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define debug if(0)
const int mod = 1e9 + 7;
const ll infL = 1e18 + 7;
const int inf = 1e9 + 7;
//void add(int &a, int b) { a = (a+b)%mod; }
//int add(int a, int b, int c) { int res = (((a+b)%mod) + c)%mod; return res; }
struct BIT {
int n; vector<ll> bit;
BIT(int size) {
n = size;
bit.assign(n, 0);
}
ll sum(int r) {
ll ret = 0;
for(; r >= 0; r = (r & (r+1))-1)
ret += bit[r];
return ret;
}
void add(int idx, ll d) {
for(; idx < n; idx = idx|(idx+1))
bit[idx] += d;
}
};
void add(BIT &b, int l, int r, ll v) {
b.add(l, v);
b.add(r+1, -v);
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, q; cin>>n>>q;
vector<ll> tr(n);
for(int i=0; i<n; i++) {
cin>>tr[i];
}
sort(tr.begin(), tr.end());
BIT bit(n+5);
for(int i=0; i<n; i++) add(bit, i+1, i+1, tr[i]);
for(int i=n+1; i<(n+5); i++) add(bit, i, i, 2*inf);
while(q--) {
char c; cin>>c;
if(c == 'C') {
int l, r; cin>>l>>r;
int lo = 1, hi = n;
while(lo < hi) {
int m = (lo+hi)/2;
if(bit.sum(m) >= l)
hi = m;
else
lo = m+1;
}
int pozp = lo; lo = 1; hi = n;
while(lo < hi) {
int m = (lo+hi+1)/2;
if(bit.sum(m) > r)
hi = m - 1;
else
lo = m;
}
int pozk = lo;
debug cerr<<"pozp: "<<pozp<<" ; pozk = "<<pozk<<"\n";
if(bit.sum(pozp) < l) {
cout<<0<<"\n";
continue;
}
int ret = pozk - pozp + 1;
cout<<ret<<"\n";
}
else {
int c, h; cin>>c>>h;
int lo = 1, hi = n;
while(lo < hi) {
int m = (lo+hi)/2;
if(bit.sum(m) >= h)
hi = m;
else
lo = m+1;
}
int pp = lo; // position of first tree with height >= h
debug cerr<<"pp: "<<pp<<"\n";
if(n-pp+1 <= c) {
debug cerr<<"all from ["<<pp<<", "<<n<<"] increased\n";
// all tree can be increased
add(bit, pp, n, 1);
continue;
}
int valk = bit.sum(pp+c-1); // value of last 'increased' element
debug cerr<<"valk = "<<valk<<"\n";
int toadd = c;
if(valk > bit.sum(pp)) {
lo = 1; hi = n;
while(lo < hi) {
int m = (lo+hi+1)/2;
if(bit.sum(m) > valk-1)
hi = m - 1;
else
lo = m;
}
int pbl = lo; // postion of last before valk
debug cerr<<"adding on ["<<pp<<", "<<pbl<<"] - 1\n";
add(bit, pp, pbl, 1);
toadd = c - (pbl-pp+1);
}
lo = 1; hi = n;
while(lo < hi) {
debug cerr<<"{lo, hi} = {"<<lo<<", "<<hi<<"}\n";
int m = (lo+hi+1)/2;
if(bit.sum(m) > valk)
hi = m - 1;
else
lo = m;
}
int pck = lo; // postiono of last great element
debug cerr<<"adding on ["<<pck-toadd+1<<", "<<pck<<"] - 2 # lo = "<<lo<<"\n";
add(bit, pck-toadd+1, pck, 1);
debug {
cerr<<"AFTER: ";
for(int i=1; i<=n; i++) cerr<<bit.sum(i)<<" ";
cerr<<"\n\n";
}
}
}
debug {
cerr<<"AFTER: ";
for(int i=1; i<=n; i++) cerr<<bit.sum(i)<<" ";
cerr<<"\n\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
2860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
324 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
46 ms |
1616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
1656 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
2420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
2500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
2648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
3412 KB |
Output is correct |
| 2 |
Incorrect |
101 ms |
2784 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
3080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
4140 KB |
Output is correct |
