#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxN = 1e5 + 1;
ll bit[mxN + 1], a[mxN + 1];
int n, m;
void upd(int pos, ll val) {
for (; pos <= mxN; pos += pos & -pos) {
bit[pos] += val;
}
}
ll qry(int pos) {
ll res = 0;
for (; pos; pos -= pos & -pos) {
res += bit[pos];
}
return res;
}
int f(ll val) {
int l = 1, r = n;
while (l <= r) {
int mid = (l + r) / 2;
if (qry(mid) >= val) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
upd(i, a[i]);
upd(i + 1, -a[i]);
}
for (int i = 0; i < m; i++) {
char ty;
cin >> ty;
if (ty == 'F') {
int c, h;
cin >> c >> h;
int left = f(h);
if (left == n + 1) continue;
int right = left + c - 1;
if (right >= n) {
upd(left, 1);
upd(n + 1, -1);
} else {
upd(left, 1);
upd(right + 1, -1);
}
} else {
ll x, y;
cin >> x >> y;
int l = f(x), r = f(y + 1);
if (l == n + 1) {
cout << 0 << "\n";
} else {
if (r == n + 1) r = n;
cout << r - l + 1 << "\n";
}
}
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |