// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int MAXN = 1e5 + 5;
int a[MAXN];
struct DataTree {
const i64 INF = 1e18;
struct Data {
i64 v, lz;
};
vector<Data> st;
DataTree (int _N) : st(4 * _N + 4) {}
Data combine(Data lf, Data rg) {
Data res;
res.v = lf.v + rg.v;
res.lz = 0;
return res;
}
void build(int id, int l, int r) {
if (l == r) {
st[id].v = a[l];
st[id].lz = 0;
return;
}
int mid = (l + r)/2;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = combine(st[id * 2], st[id * 2 + 1]);
// cout << id << " " << st[id].v << " " << st[id].lz << "\n";
}
void push(int id, int l, int r) {
i64 &add = st[id].lz;
int mid = (l + r)/2;
st[id * 2].v += add * (l - mid + 1);
st[id * 2 + 1].v += add * (r - mid);
st[id * 2].lz += add;
st[id * 2 + 1].lz += add;
add = 0;
return;
}
void update(int id, int l, int r, int u, int v, i64 x) {
if (v < l || u > r) return;
if (u <= l && r <= v) {
st[id].v += x * (r - l + 1);
st[id].lz += x;
return;
}
push(id, l, r);
int mid = (l + r)/2;
update(id * 2, l, mid, u, v, x);
update(id * 2 + 1, mid + 1, r, u, v, x);
st[id] = combine(st[id * 2], st[id * 2 + 1]);
}
Data get(int id, int l, int r, int u, int v) {
if (v < l || u > r) return {0, 0};
if (u <= l && r <= v) return st[id];
push(id, l, r);
int mid = (l + r)/2;
return combine(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v));
}
};
void Solve(void) {
int N, Q; cin >> N >> Q;
for (int i = 1; i <= N; i ++) cin >> a[i];
sort(a + 1, a + N + 1);
DataTree T(N + 2); T.build(1, 1, N);
while (Q --) {
char op; int C, H; cin >> op >> C >> H;
if (op == 'F') {
int l = 1, h = N;
while (l <= h) {
int mid = (l + h)/2;
if (T.get(1, 1, N, mid, mid).v >= H) h = mid - 1;
else l = mid + 1;
}
// l = first to increase
int lf = l;
int rg = min(l + C - 1, N);
int mx = T.get(1, 1, N, rg, rg).v;
// find the biggest id that = mx
l = 1, h = N;
while (l <= h) {
int mid = (l + h)/2;
if (T.get(1, 1, N, mid, mid).v > mx) h = mid - 1;
else l = mid + 1;
}
int rgg = h;
// find the smallest id that = mx
l = 1, h = N;
while (l <= h) {
int mid = (l + h)/2;
if (T.get(1, 1, N, mid, mid).v >= mx) h = mid - 1;
else l = mid + 1;
}
int lff = l;
int gap = rg - lff + 1;
// cout << mx << "\n";
// cout << lf << " " << lff - 1 << " " << rgg - gap + 1 << " " << rgg << "\n";
T.update(1, 1, N, lf, lff - 1, 1);
T.update(1, 1, N, rgg - gap + 1, rgg, 1);
} else {
int l = 1, h = N;
while (l <= h) {
int mid = (l + h)/2;
if (T.get(1, 1, N, mid, mid).v >= C) h = mid - 1;
else l = mid + 1;
}
int lf = l;
l = 1, h = N;
while (l <= h) {
int mid = (l + h)/2;
if (T.get(1, 1, N, mid, mid).v > H) h = mid - 1;
else l = mid + 1;
}
cout << h - lf + 1 << "\n";
}
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(10);
int Tests = 1; // cin >> Tests;
while (Tests --) {
Solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
299 ms |
7504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| 2 |
Correct |
5 ms |
604 KB |
Output is correct |
| 3 |
Correct |
5 ms |
604 KB |
Output is correct |
| 4 |
Correct |
3 ms |
472 KB |
Output is correct |
| 5 |
Correct |
150 ms |
1612 KB |
Output is correct |
| 6 |
Incorrect |
196 ms |
2000 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
190 ms |
2120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
2064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
299 ms |
5812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
414 ms |
6608 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
351 ms |
6688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
482 ms |
7764 KB |
Output is correct |
| 2 |
Incorrect |
452 ms |
6740 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
402 ms |
7512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
9296 KB |
Output is correct |
