#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 1e5+10;
int bit[mxN], n;
void add(int l, int r, int x) {
for(; l <= n; l += (l & (-l))) bit[l] += x;
for(++r; r <= n; r += (r & (-r))) bit[r] -= x;
}
int query(int x) {
int sum = 0;
for(; x >= 1; x -= (x & (-x))) sum += bit[x];
return sum;
}
int qry(int l1, int r1, auto f) {
int l = l1, r = r1+1;
while(l < r) {
int mid = l + (r - l) / 2;
if(f(mid)) r = mid;
else l = mid+1;
}
return l;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> n >> q;
vector<int> v(n+1);
for(int i = 1; i <= n; i++) {
cin >> v[i];
}
sort(v.begin(), v.end());
for(int i = 1; i <= n; i++) add(i, i, v[i]);
while(q--) {
char flag;
cin >> flag;
if(flag == 'F') {
int c, h;
cin >> c >> h;
int l = qry(1, n, [&](int x) {return query(x) >= h;});
if(l == n+1) continue;
int r = l + c - 1;
if(r >= n) {
add(l, n, 1);
continue;
}
int x = query(r);
int l1 = qry(l, n, [&](int i) { return query(i) >= x;});
int r1 = qry(l1, n, [&](int i) {return query(i) > x;}) - 1;
add(l, l1-1, 1);
add(r1 - (c - (l1 - l)) + 1, r1, 1);
}
else {
int mn, mx;
cin >> mn >> mx;
int l = qry(1, n, [&](int i) {return query(i) >= mn;});
int r = qry(1, n, [&](int i) {return query(i) > mx;});
cout << r-l << '\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... |