#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
int N, M, A[100010];
struct node {
int s,e,m,val,lazy;
node *l, *r;
node(int _s, int _e) {
s = _s, e = _e, m = (s+e)/2;
val = 0, lazy = 0;
if (s != e) {
l = new node(s, m);
r = new node(m+1,e);
}
}
void pushdown() {
val += lazy;
if (s != e) {
l->lazy += lazy;
r->lazy += lazy;
}
lazy = 0;
}
void add(int qs, int qe, int v) {
if (qe < qs) return;
if (qs == s && qe == e) lazy += v;
else {
if (qs > m) r->add(qs, qe, v);
else if (qe <= m) l->add(qs, qe, v);
else l->add(qs, m, v), r->add(m+1, qe, v);
l->pushdown(), r->pushdown();
val = max(l->val, r->val);
}
}
int find(int v) { // index of first element >= v
if (s == e) return s;
if (val < v) return r->find(v);
if (l->val >= v) return l->find(v);
return r->find(v);
}
int get(int qs, int qe) {
pushdown();
if (qs <= s && qe >= e) return val;
if (qs > m) return r->get(qs, qe);
if (qe <= m) return l->get(qs, qe);
return max(l->get(qs, m), r->get(m + 1, qe));
}
} *seg;
signed main() {
fast;
cin >> N >> M;
for (int i = 1; i <= N; ++i) cin >> A[i];
sort(A + 1, A + 1 + N);
seg = new node(1, N);
for (int i = 1; i <= N; ++i) seg->add(i, i, A[i]);
while (M--) {
char op; int a, b; cin >> op >> a >> b;
if (op == 'F') {
int st = seg->find(b);
int high = seg->get(min(N, st + a - 1), min(N, st + a - 1));
int mid = seg->find(high);
int en = seg->find(high + 1);
if (mid > st) --mid;
if (seg->get(en, en) > high) --en;
int rem = a - (mid - st + 1);
seg->add(st, mid, 1);
seg->add(max(mid + 1, en - rem + 1), en, 1);
} else {
int lx = seg->find(a);
int rx = seg->find(b + 1);
if (seg->get(lx, lx) < a) {cout << 0 << '\n'; continue;}
if (seg->get(rx, rx) > b) --rx;
cout << rx - lx + 1 << '\n';
}
// for (int i = 1; i <= N; ++i) cout << seg->get(i, i) << ' ';
// cout << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
13196 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
2352 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
2504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
9992 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
92 ms |
11968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
186 ms |
13408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
13004 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
159 ms |
15640 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
