/**
* author : Lăng Trọng Đạt
* created: 28-04-2024
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;
const int MAXN = 1e5 + 5;
int g[MAXN];
int n;
struct Node {
int add = 0, mx = 0;
} st[4*MAXN];
void build(int v = 1, int l = 1, int r = n) {
if (l == r) st[v].mx = g[l];
else {
int mid = (l + r) / 2;
build(2*v, l, mid);
build(2*v + 1, mid + 1, r);
st[v].mx = max(st[2*v].mx, st[2*v + 1].mx);
}
}
void push(int v, int l, int r) {
st[v].mx += st[v].add;
if (l < r) {
st[2*v].add += st[v].add;
st[2*v + 1].add += st[v].add;
}
st[v].add = 0;
}
void upd(int p, int q, int v = 1, int l = 1, int r = n) {
if (l > q or p > r) return;
if (p <= l && r <= q) {
st[v].add++;
}
else {
int mid = (l + r) / 2;
upd(p, q, 2*v, l, mid);
upd(p, q, 2*v + 1, mid + 1, r);
push(2*v, l, mid);
push(2*v + 1, mid + 1, r);
st[v].mx = max(st[2*v].mx, st[2*v + 1].mx);
}
}
int get_index(int x, int v = 1, int l = 1, int r = n) {
push(v, l, r);
x -= st[v].add;
if (l == r) return (x > st[v].mx ? n + 1 : l);
int mid = (l + r) / 2;
if (x <= st[2*v].mx) {
return get_index(x, 2*v, l, mid);
} else {
return get_index(x, 2*v + 1, mid + 1, r);
}
}
int get_val(int p, int v = 1, int l = 1, int r = n) {
push(v, l, r);
if (l > p or p > r) return 0;
if (l == r) return st[v].mx;
else {
int mid = (l + r) / 2;
return get_val(p, 2*v, l, mid) + get_val(p, 2*v + 1, mid + 1, r);
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("hi.inp", "r")) {
freopen("hi.inp", "r", stdin);
// freopen("hi.out", "w", stdout);
}
int m, c, h;
char type;
cin >> n >> m;
FOR(i, 1, n) {
cin >> g[i];
}
sort(g, g + n + 1);
build();
FOR(i, 1, m) {
cin >> type >> c >> h;
if (type == 'F') {
int l_id = get_index(h);
db(l_id)
if (l_id + c - 1 >= n) {
upd(l_id, n);
} else {
int r_val = get_val(l_id + c);
int vach = get_index(r_val) - 1;
if (l_id <= vach)
upd(l_id, vach);
int cuoi = get_index(r_val + 1) - 1;
upd(cuoi - (c - (vach - l_id + 1)) + 1, cuoi);
db(c, h, l_id, r_val, cuoi, vach)
db(cuoi - (c - (vach - l_id + 1)) + 1)
}
} else {
db(c, h, get_index(c), get_index(h))
cout << get_index(h + 1) - get_index(c) << "\n";
}
}
}
Compilation message
grow.cpp: In function 'int32_t main()':
grow.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
| ^
grow.cpp:97:5: note: in expansion of macro 'FOR'
97 | FOR(i, 1, n) {
| ^~~
grow.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
| ^
grow.cpp:102:5: note: in expansion of macro 'FOR'
102 | FOR(i, 1, m) {
| ^~~
grow.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
90 | freopen("hi.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
28 ms |
5724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
5968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
6164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
8528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
8272 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
9112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
8524 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
9664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
