#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
const int mxn = 1e5 + 3;
const int inf = 1e7;
int n, q;
int mx[4 * mxn + 1], lz[4 * mxn + 1], a[mxn + 1];
void push(int nd){
mx[nd * 2] += lz[nd]; mx[nd * 2 + 1] += lz[nd]; lz[nd * 2] += lz[nd];
lz[nd * 2 + 1] += lz[nd]; lz[nd] = 0;
}
void upd(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
mx[nd] += v; lz[nd] += v;
return;
}
int mid = (l + r) >> 1;
push(nd);
upd(nd * 2, l, mid, ql, qr, v); upd(nd * 2 + 1, mid + 1, r, ql, qr, v);
mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]);
}
int getv(int nd, int l, int r, int id){
if(l == r)return(mx[nd]);
int mid = (l + r) >> 1;
push(nd);
if(id <= mid)return(getv(nd * 2, l, mid, id));
else return(getv(nd * 2 + 1, mid + 1, r, id));
}
int findl(int nd, int l, int r, int h){
if(l == r)return(l);
int mid = (l + r) >> 1;
push(nd);
if(mx[nd * 2] >= h){
return(findl(nd * 2, l, mid, h));
}else{
return(findl(nd * 2 + 1, mid + 1, r, h));
}
}
int findr(int nd, int l, int r, int h){
if(l == r)return(r - 1);
int mid = (l + r) >> 1;
push(nd);
if(mx[nd * 2] > h){
return(findr(nd * 2, l, mid, h));
}else{
return(findr(nd * 2 + 1, mid + 1, r, h));
}
}
void add(int c, int h){
int l = findl(1, 1, n + 1, h);
if(l == n + 1)return;
int r = min(l + c - 1, n), v = getv(1, 1, n + 1, r);
int rl = findl(1, 1, n + 1, v), rr = findr(1, 1, n + 1, v);
if(l == rl){
upd(1, 1, n + 1, max(rr - c + 1, l), rr, 1);
}else{
upd(1, 1, n + 1, l, rl - 1, 1);
int lft = rr - (c - (rl - l)) + 1;
upd(1, 1, n + 1, lft, rr, 1);
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++)cin >> a[i];
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; i++)upd(1, 1, n + 1, i, i, a[i]);
forr(i, 0, q){
char idq; cin >> idq;
if(idq == 'F'){
int c, h; cin >> c >> h;
add(c, h);
/*
for(int j = 1; j <= n; j++)cout << getv(1, 1, n + 1, j) << " ";
cout << "\n";
*/
}else{
int l, r; cin >> l >> r;
cout << findr(1, 1, n + 1, r) - findl(1, 1, n + 1, l) + 1 << "\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
5180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
340 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
340 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
820 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
2952 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
85 ms |
5056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
72 ms |
5052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
5192 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
5224 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
5636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
