#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
using namespace std;
const int mxN = 3e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
int n , q;
int a[mxN];
int t[mxN * 4];
int lazy[mxN * 4];
void build(int v , int tl , int tr)
{
if(tl == tr) t[v] = a[tl];
else {
int tm = (tl + tr) / 2;
build(v * 2 , tl , tm);
build(v * 2 + 1 , tm + 1 , tr);
t[v] = max(t[v * 2] , t[v * 2 + 1]);
}
}
void modify(int v)
{
t[v * 2] += lazy[v];
t[v * 2 + 1] += lazy[v];
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
lazy[v] = 0;
}
void update(int v , int tl , int tr , int l , int r)
{
if(l > r) return ;
if(tl == l && tr == r) {
t[v]++;
lazy[v]++;
return;
}
int tm = (tl + tr) / 2;
modify(v);
update(v * 2 , tl , tm , l , min(r , tm));
update(v * 2 + 1 , tm + 1 , tr , max(l , tm + 1) , r);
t[v] = max(t[v * 2] , t[v * 2 + 1]);
}
int findfst(int v , int tl , int tr , int x)
{
if(t[v] < x) return n + 1;
if(tl == tr) return tl;
modify(v);
int tm = (tl + tr) / 2;
if(t[v * 2] >= x) return findfst(v * 2 , tl , tm , x);
return findfst(v * 2 + 1 , tm + 1 , tr , x);
}
int getidx(int v , int tl , int tr , int pos)
{
if(tl == tr && tl == pos) return t[v];
modify(v);
int tm = (tl + tr) / 2;
if(pos <= tm) return getidx(v * 2 , tl , tm , pos);
return getidx(v * 2 + 1 , tm + 1 , tr , pos);
}
int getidx(int pos)
{
return getidx(1 , 1 , n , pos);
}
int findfst(int x)
{
return findfst(1 , 1 , n , x);
}
void update(int l , int r)
{
update(1 , 1 , n , l , r);
}
void solve()
{
cin >> n >> q;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
sort(a + 1 , a + 1 + n);
build(1 , 1 , n);
while(q--) {
char cmd;
cin >> cmd;
if(cmd == 'F') {
int c , h;
cin >> c >> h;
int l1 = findfst(h);
int r1 = min(n , l1 + c - 1);
int val = getidx(r1);
int r2 = findfst(val);
update(l1 , r2 - 1);
int r3 = findfst(val + 1);
int re = c - max(0 , (r2 - 1 - l1 + 1));
update(max(r2 , r3 - 1 - re + 1) , r3 - 1);
}
else {
int l , r;
cin >> l >> r;
cout << findfst(r + 1) - 1 - findfst(l) + 1 << endl;
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen(TASK".in" , "r" , stdin);
//freopen(TASK".out" , "w" , stdout);
int tc = 1;
//cin >> tc;
while(tc--) {
solve();
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
3920 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
2 ms |
336 KB |
Output is correct |
| 3 |
Correct |
2 ms |
336 KB |
Output is correct |
| 4 |
Correct |
2 ms |
328 KB |
Output is correct |
| 5 |
Correct |
36 ms |
1456 KB |
Output is correct |
| 6 |
Incorrect |
41 ms |
1724 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
39 ms |
1632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
1700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
53 ms |
2580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
3780 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
4348 KB |
Output is correct |
| 2 |
Incorrect |
104 ms |
3972 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
65 ms |
4084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
5048 KB |
Output is correct |
