#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;
void setIO() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
struct SegTree {
int n;
vector<int> v;
vector<ll> tree;
vector<ll> lazy;
SegTree(vector<int> const &_v) {
this->v = _v;
n = sz(v);
tree.resize(4*n+5, 0);
lazy.resize(4*n+5, 0);
}
void push(int u, int tl, int tr) {
if(lazy[u] == 0) return ;
tree[u] += (tr - tl + 1) * lazy[u];
if(tl != tr) {
lazy[2*u] += lazy[u];
lazy[2*u+1] += lazy[u];
}
lazy[u] = 0;
}
void build(int u, int tl, int tr) {
if(tl == tr) {
tree[u] = v[tl];
} else {
int tm = (tl + tr) / 2;
build(2*u, tl, tm);
build(2*u+1, tm+1, tr);
tree[u] = tree[2*u] + tree[2*u+1];
}
}
void update(int u, int tl, int tr, int l, int r, int val) {
push(u, tl, tr);
if(tl > tr || l > tr || tl > r) return ;
if(l <= tl && tr <= r) {
lazy[u] += val;
push(u, tl, tr);
return ;
}
int tm = (tl + tr) / 2;
update(2*u, tl, tm, l, r, val);
update(2*u+1, tm+1, tr, l, r, val);
tree[u] = tree[2*u] + tree[2*u+1];
}
ll query(int u, int tl, int tr, int pos) {
if(tl > tr || tl > pos || pos > tr) return 0;
push(u, tl, tr);
if(tl == tr) return tree[u];
int tm = (tl + tr) / 2;
if(pos <= tm)
return query(2*u, tl, tm, pos);
return query(2*u+1, tm+1, tr, pos);
}
void update(int l, int r, int val) {
update(1, 0, n-1, l, r, val);
}
ll query(int pos) {
return query(1, 0, n-1, pos);
}
};
int32_t main() {
setIO();
int n, q;
cin >> n >> q;
vector<int> v(n);
for(int &x : v) cin >> x;
sort(all(v));
SegTree tree(v);
tree.build(1, 0, n-1);
auto binSearch = [&](int l, int r, function<bool(int)> f) {
int ans = n;
while(l <= r) {
int mid = (l + r) / 2;
if(f(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
return ans;
};
while(q--) {
char t;
cin >> t;
if(t == 'F') {
int c, h;
cin >> c >> h;
int q_l = binSearch(0, n-1, [&](int x) {
return tree.query(x) >= h;
});
int q_r = q_l + c - 1;
if(q_r >= n-1) {
tree.update(q_l, q_r, 1);
continue;
}
int newL = binSearch(q_l, n-1, [&](int x) {
return tree.query(x) >= tree.query(q_r);
});
int newR = binSearch(newL, n-1, [&](int x) {
return tree.query(x) > tree.query(q_r);
}) - 1;
tree.update(q_l, newL-1, 1);
tree.update(newR - c + newL - q_l + 1, newR, 1);
// for(int i=0; i<n; i++)
// cout << tree.query(i) << " ";
// cout << '\n';
} else {
int a, b;
cin >> a >> b;
if(tree.query(n-1) < a) {
cout << 0 << '\n';
continue;
}
int l = binSearch(0, n-1, [&](int x) {
return tree.query(x) >= a;
});
int r = binSearch(0, n-1, [&](int x) {
return tree.query(x) > b;
});
cout << r - l << '\n';
}
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
279 ms |
7804 KB |
Output is correct |
2 |
Correct |
432 ms |
8088 KB |
Output is correct |
3 |
Correct |
132 ms |
7752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
468 KB |
Output is correct |
2 |
Correct |
3 ms |
468 KB |
Output is correct |
3 |
Correct |
5 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
464 KB |
Output is correct |
5 |
Correct |
128 ms |
1740 KB |
Output is correct |
6 |
Correct |
160 ms |
1892 KB |
Output is correct |
7 |
Correct |
13 ms |
724 KB |
Output is correct |
8 |
Correct |
61 ms |
1344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
127 ms |
2084 KB |
Output is correct |
2 |
Correct |
163 ms |
2124 KB |
Output is correct |
3 |
Correct |
3 ms |
724 KB |
Output is correct |
4 |
Correct |
79 ms |
1712 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
111 ms |
2252 KB |
Output is correct |
2 |
Correct |
183 ms |
2088 KB |
Output is correct |
3 |
Correct |
30 ms |
852 KB |
Output is correct |
4 |
Correct |
158 ms |
2152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
282 ms |
6076 KB |
Output is correct |
2 |
Correct |
402 ms |
6816 KB |
Output is correct |
3 |
Correct |
41 ms |
1876 KB |
Output is correct |
4 |
Correct |
104 ms |
6724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
371 ms |
6708 KB |
Output is correct |
2 |
Correct |
395 ms |
7240 KB |
Output is correct |
3 |
Correct |
130 ms |
6792 KB |
Output is correct |
4 |
Correct |
40 ms |
1952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
273 ms |
7060 KB |
Output is correct |
2 |
Correct |
273 ms |
7824 KB |
Output is correct |
3 |
Correct |
132 ms |
7608 KB |
Output is correct |
4 |
Correct |
40 ms |
1876 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
440 ms |
8080 KB |
Output is correct |
2 |
Correct |
417 ms |
7080 KB |
Output is correct |
3 |
Correct |
64 ms |
8084 KB |
Output is correct |
4 |
Correct |
237 ms |
7852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
342 ms |
7884 KB |
Output is correct |
2 |
Correct |
413 ms |
8152 KB |
Output is correct |
3 |
Correct |
662 ms |
9168 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
270 ms |
9520 KB |
Output is correct |