#include<bits/stdc++.h>
using namespace std;
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif
using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;
#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
cout << "[";
for (auto it = v.begin(); it != v.end();) {
cout << *it;
if (++it != v.end()) cout << ", ";
}
return cout << "]";
}
//var
LL T;
template<typename T>
struct fen {
vector<T> tr;
LL mxn;
fen(LL sz) {
mxn = sz;
tr.assign(sz + 5, 0);
}
void upd(LL g, T k) {
g++;
assert(g != 0);
for (; g <= mxn; g += g&-g)
tr[g] += k;
}
T ge(LL g) {
g++;
T res = 0;
for (; g; g -= g&-g)
res += tr[g];
return res;
}
T rng(LL l, LL r) { return ge(r) - ge(l - 1); }
//maxi and mini only work with positive numbers
LL maxi(T k) {
//max i such that ge(i) <= k.
//log(n) vs log^2(n) binary search
T running = 0; LL res = 0;
LL lg = 32 - __builtin_clz(mxn);
for (int i = lg; i>=0; i--) {
if (res + (1LL << i) > mxn) continue;
if (running + tr[res + (1LL << i)] > k) continue;
running += tr[res + (1LL << i)];
res += (1LL << i);
}
return res;
}
LL mini(T k) {
//kth order statistic
T running = 0; LL res = 0;
LL lg = 32 - __builtin_clz(mxn);
for (int i = lg; i>=0; i--) {
if (res + (1LL << i) > mxn) continue;
if (running + tr[res + (1LL << i)] >= k) continue;
running += tr[res + (1LL << i)];
res += (1LL << i);
}
return res + 1;
}
};
void solve() {
LL n, m;
cin >> n >> m;
vector<LL> a(n);
for (auto& u : a)
cin >> u;
sort(all(a));
fen<LL> delt(n);
auto get = [&](LL in) -> LL {
return a[in] + delt.ge(in);
};
auto up_range = [&](LL l, LL r, LL k) -> void {
if (l > r) return;
delt.upd(l, 1);
delt.upd(r + 1, -1);
};
auto find_low = [&](LL in) -> LL {
//finds lowest index point with value equal to index
LL target = get(in);
LL lo = 0, hi = in, mid;
while (lo < hi) {
mid = (lo + hi) >> 1;
if (get(mid) == target)
hi = mid;
else lo = mid + 1;
}
return lo;
};
auto find_high = [&](LL in) -> LL {
LL target = get(in);
LL lo = in, hi = n - 1, mid;
while (lo < hi) {
mid = (lo + hi + 1) >> 1;
if (get(mid) == target)
lo = mid;
else hi = mid - 1;
}
return lo;
};
auto find_point = [&](LL k) -> LL {
//finds minimal index with value >= k
LL lo = 0, hi = n, mid;
while (lo < hi) {
mid = (lo + hi) >> 1;
if (get(mid) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
};
while (m--) {
char T; cin >> T;
/*F0R (i, n) debug(get(i));
debug('\n');*/
if (T == 'F') {
LL c, q;
cin >> q >> c;
LL l = find_point(c);
if (l == n) continue;
LL r = min(n - 1, c + q - 1);
LL low = find_low(r);
LL high = find_high(r);
up_range(l, low - 1, 1);
LL used = max(low - l, 0LL);
LL rem = q - used;
//update last rem
rem = min(rem, high - low + 1);
up_range(high - rem + 1, high, 1);
} else {
LL lo, hi; cin >> lo >> hi;
LL r = find_point(hi + 1); r--;
LL l = find_point(lo);
cout << r - l + 1 << "\n";
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
T = 1;
//cin >> T;
FOR(t, T)
solve();
cout.flush();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
2884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
1512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
1688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
58 ms |
2400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
57 ms |
2672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
45 ms |
2632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
100 ms |
3372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
2956 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
99 ms |
4116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
