#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44
using namespace std;
typedef struct Treap *T;
typedef pair <T, T> PTT;
T NIL;
struct Treap {
Treap *left, *right;
int val, mx, lazy;
int sz;
int prio;
Treap(int _val) {
left = right = NIL;
val = mx = _val;
lazy = 0;
sz = 1;
prio = rand();
}
};
T root = NIL;
inline void refresh(T nod) {
nod -> sz = 1 + nod -> left -> sz + nod -> right -> sz;
nod -> mx = max(nod -> val, max(nod -> left -> mx, nod -> right -> mx));
}
inline void solve_lazy(T nod) {
nod -> left -> lazy += nod -> lazy;
nod -> right -> lazy += nod -> lazy;
nod -> val += nod -> lazy;
nod -> lazy = 0;
}
T join(T a, T b) {
if(a == NIL) {
return b;
}
if(b == NIL) {
return a;
}
solve_lazy(a);
solve_lazy(b);
if(a -> prio > b -> prio) {
a -> right = join(a -> right, b);
refresh(a);
return a;
}
b -> left = join(a, b -> left);
refresh(b);
return b;
}
PTT split_val(T nod, int val) {
if(nod == NIL) {
return {NIL, NIL};
}
solve_lazy(nod);
if(nod -> val > val) {
PTT aux = split_val(nod -> left, val);
nod -> left = aux.second;
refresh(nod);
return {aux.first, nod};
}
PTT aux = split_val(nod -> right, val);
nod -> right = aux.first;
refresh(nod);
return {nod, aux.second};
}
PTT split_sz(T nod, int sz) {
if(nod == NIL) {
return {NIL, NIL};
}
solve_lazy(nod);
if(nod -> left -> sz >= sz) {
PTT aux = split_sz(nod -> left, sz);
nod -> left = aux.second;
refresh(nod);
return {aux.first, nod};
}
PTT aux = split_sz(nod -> right, sz - nod -> left -> sz - 1);
nod -> right = aux.first;
refresh(nod);
return {nod, aux.second};
}
/*void dfs(T nod) {
if(nod == NIL) {
return ;
}
solve_lazy(nod);
dfs(nod -> left);
cerr << nod -> val << " ";
dfs(nod -> right);
refresh(nod);
}*/
int main() {
//ifstream cin("B.in");
//ofstream cout("B.out");
int i, n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
NIL = new Treap(0);
NIL -> left = NIL -> right = NIL;
NIL -> sz = NIL -> prio = NIL -> val = NIL -> mx = NIL -> lazy = 0;
root = NIL;
cin >> n >> m;
vector <int> arr;
for(i = 1; i <= n; i++) {
int h;
cin >> h;
arr.push_back(h);
}
sort(arr.begin(), arr.end());
for(auto it : arr) {
T aux = new Treap(it);
root = join(root, aux);
}
while(m > 0) {
m--;
char ch;
cin >> ch;
if(ch == 'F') {
int c, h;
cin >> c >> h;
PTT aux1 = split_val(root, h - 1);
PTT aux2 = split_sz(aux1.second, min(aux1.second -> sz, c));
//cerr << aux1.second -> sz << "\n";
int val = aux2.first -> mx;
PTT aux3 = split_val(aux2.first, val - 1);
aux3.first -> lazy++;
aux3.second -> lazy++;
PTT aux4 = split_val(aux2.second, val);
root = join(aux1.first, join(aux3.first, join(aux4.first, join(aux3.second, aux4.second))));
//cerr << aux1.first -> sz << " " << aux2.first -> sz << " " << aux2.second -> sz << "\n";
}
else {
int l, r;
cin >> l >> r;
PTT aux1 = split_val(root, r);
PTT aux2 = split_val(aux1.first, l - 1);
cout << aux2.second -> sz << "\n";
root = join(join(aux2.first, aux2.second), aux1.second);
}
//dfs(root);
//cerr << "\n";
}
//cin.close();
//cout.close();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
6132 KB |
Output is correct |
| 2 |
Correct |
184 ms |
7676 KB |
Output is correct |
| 3 |
Correct |
101 ms |
9048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
9048 KB |
Output is correct |
| 2 |
Correct |
5 ms |
9048 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9048 KB |
Output is correct |
| 4 |
Correct |
4 ms |
9048 KB |
Output is correct |
| 5 |
Correct |
84 ms |
9048 KB |
Output is correct |
| 6 |
Correct |
99 ms |
9048 KB |
Output is correct |
| 7 |
Correct |
8 ms |
9048 KB |
Output is correct |
| 8 |
Correct |
33 ms |
9048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
9328 KB |
Output is correct |
| 2 |
Correct |
97 ms |
10268 KB |
Output is correct |
| 3 |
Correct |
4 ms |
10268 KB |
Output is correct |
| 4 |
Correct |
48 ms |
10968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
12172 KB |
Output is correct |
| 2 |
Correct |
106 ms |
13140 KB |
Output is correct |
| 3 |
Correct |
17 ms |
13140 KB |
Output is correct |
| 4 |
Correct |
98 ms |
14388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
18132 KB |
Output is correct |
| 2 |
Correct |
196 ms |
19720 KB |
Output is correct |
| 3 |
Correct |
38 ms |
19720 KB |
Output is correct |
| 4 |
Correct |
90 ms |
21188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
22632 KB |
Output is correct |
| 2 |
Correct |
189 ms |
24060 KB |
Output is correct |
| 3 |
Correct |
93 ms |
25152 KB |
Output is correct |
| 4 |
Correct |
33 ms |
25152 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
27140 KB |
Output is correct |
| 2 |
Correct |
149 ms |
28736 KB |
Output is correct |
| 3 |
Correct |
96 ms |
29796 KB |
Output is correct |
| 4 |
Correct |
33 ms |
29796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
191 ms |
32200 KB |
Output is correct |
| 2 |
Correct |
199 ms |
32924 KB |
Output is correct |
| 3 |
Correct |
58 ms |
34628 KB |
Output is correct |
| 4 |
Correct |
93 ms |
35328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
178 ms |
36528 KB |
Output is correct |
| 2 |
Correct |
187 ms |
38208 KB |
Output is correct |
| 3 |
Correct |
225 ms |
40408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
42704 KB |
Output is correct |
