#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = (l); i < r; ++i)
#define NN 100010
namespace seg {
typedef ll T;
T id=0;
T f(T a, T b) {return a+b;}
T t[2 * NN];
ll n=NN; // array size
void _modify(ll p, T value) { // set value at position p
for (p+=n, t[p] += value; p /= 2;) t[p] = f(t[2*p], t[2*p+1]);
}
T _query(ll l, ll r) { // fold f on interval [l, r)
T resl=id, resr=id;
for (l += n, r += n; l < r; l /= 2, r /= 2) {
if (l&1) resl = f(resl, t[l++]);
if (r&1) resr = f(t[--r], resr);
}
return f(resl, resr);
}
void modify(ll l, ll r, ll T) { // already inclusive exclusive we smart about it
if (l>=r) return; // nothing should happen
_modify(l, T);
_modify(r, -T);
}
T query(ll i) {
return _query(0, i+1);
}
}
ll n;
pl get(ll lo, ll hi) {
pl res;
{
ll l = -1, r = n;
while (l+1<r){
ll m =(l+r)/2;
if (seg::query(m) < lo) l = m;
else r = m;
}
res.K = r;
}
{
ll l = -1, r = n;
while (l+1<r){
ll m =(l+r)/2;
if (seg::query(m) <= hi) l = m;
else r = m;
}
res.V = r;
}
return res;
}
int main(){
// freopen("a.in", "r", stdin);
// freopen("a.out", "w", stdout);
ios_base::sync_with_stdio(false); cin.tie(0);
cout << fixed << setprecision(20);
cin >> n; G(q)
vector<ll> v;
F(i, 0, n) {
G(x) v.push_back(x);
}
sort(A(v));
F(i, 0, n) {
seg::modify(i, i+1, v[i]);
}
while (q--) {
GS(s) if (s == "F") {
G(c) G(h)
auto [st, _] = get(h, 2e9);
// cout << "YA " << st << endl;
// cout << "?? " << n-1 << " " << st << " " << c-1 << endl;
ll want = seg::query(min(n-1, st + c - 1));
// cout << "HELLO? " << want << endl;
auto [tl, tr] = get(want, want);
// cout << "WTF " << tl << " " << tr << endl;
seg::modify(st, tl, 1); c -= tl - st;
seg::modify(max(tl, tr-c), tr, 1);
// cout << "Added 1 to " << st << ", " << tl-1 << " and " << max(tl, tr-c) << ", " << tr << endl;
} else {
G(a) G(b)
auto [l, r] = get(a, b);
cout << r-l << '\n';
}
// F(i, 0, n) cout << seg::query(i) << " "; cout << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
138 ms |
3896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
4 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
344 KB |
Output is correct |
| 5 |
Correct |
97 ms |
1700 KB |
Output is correct |
| 6 |
Incorrect |
110 ms |
1876 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
87 ms |
1816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
1808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
148 ms |
3096 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
230 ms |
3276 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
126 ms |
3412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
4380 KB |
Output is correct |
| 2 |
Incorrect |
278 ms |
3688 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
193 ms |
3940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
229 ms |
5044 KB |
Output is correct |
