#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <numeric>
using namespace std;
typedef long long int ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vll> vvll;
typedef vector<pll> vpll;
typedef map<ll, ll> mll;
#define rep(i, a, b) for (ll i = a; i < b; i++)
#define mp(a, b) make_pair(a, b)
#define all(a) a.begin(), a.end()
#define resz(a, b) a.resize(b)
#define sz(a) a.size()
#define fill_sz(a, x) fill_n(a.begin(), sz(a), x)
const ll H = 1000000001;
const pll none = mp(H, -1);
ll N, M;
vpll segtree;
vll lazy;
vpll left_right;
vll trees;
pll combine(pll a, pll b) {
return mp(min<ll>(a.first, b.first), max<ll>(a.second, b.second));
}
void propagate(ll cur) {
segtree[cur] = mp(segtree[cur].first + lazy[cur], segtree[cur].second + lazy[cur]);
if (left_right[cur].first != left_right[cur].second) {
lazy[2 * cur] += lazy[cur];
lazy[2 * cur + 1] += lazy[cur];
}
lazy[cur] = 0;
}
void build(ll cur, ll l, ll r) {
left_right[cur] = mp(l, r);
lazy[cur] = 0;
if (l == r) {
segtree[cur] = mp(trees[l], trees[l]);
return;
}
ll m = (l + r) / 2;
build(2 * cur, l, m);
build(2 * cur + 1, m + 1, r);
segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}
pll query(ll cur, ll l, ll r) {
propagate(cur);
if ((left_right[cur].first > r) or (left_right[cur].second < l)) {
return none;
}
if ((left_right[cur].first >= l) and (left_right[cur].second <= r)) {
return segtree[cur];
}
return combine(query(2 * cur, l, r), query(2 * cur + 1, l, r));
}
void add_range(ll cur, ll l, ll r, ll x) {
propagate(cur);
if ((left_right[cur].first > r) or (left_right[cur].second < l)) {
return;
}
if ((left_right[cur].first >= l) and (left_right[cur].second <= r)) {
lazy[cur] += x;
propagate(cur);
return;
}
add_range(2 * cur, l, r, x);
add_range(2 * cur + 1, l, r, x);
segtree[cur] = combine(segtree[2 * cur], segtree[2 * cur + 1]);
}
// find first index of tree with height ≥ h
ll first_of_height(ll cur, ll h) {
propagate(cur);
//if (segtree[cur].second < h) return -1;
if (segtree[cur].second < h) return N;
if (left_right[cur].first == left_right[cur].second) return left_right[cur].first;
ll res = first_of_height(2 * cur, h);
if (res != N) return res;
return first_of_height(2 * cur + 1, h);
}
ll last_of_height(ll cur, ll h) {
propagate(cur);
if (segtree[cur].first > h) return -1;
if (left_right[cur].first == left_right[cur].second) return left_right[cur].first;
ll res = last_of_height(2 * cur + 1, h);
if (res != -1) return res;
return last_of_height(2 * cur, h);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> M;
resz(trees, N);
resz(segtree, 4 * N);
resz(lazy, 4 * N);
resz(left_right, 4 * N);
rep(i, 0, N) {
cin >> trees[i];
}
sort(all(trees));
build(1, 0, N - 1);
rep(q, 0, M) {
char type;
cin >> type;
if (type == 'F') {
ll c, h;
cin >> c >> h;
ll i = first_of_height(1, h);
c = min<ll>(c, N - i);
ll h2 = query(1, i + c - 1, i + c - 1).first;
ll j = first_of_height(1, h2);
ll k = last_of_height(1, h2);
add_range(1, i, j - 1, 1);
add_range(1, k + j + 1 - c - i, k, 1);
} else { // (type == 'C')
ll l, r;
cin >> l >> r;
l = first_of_height(1, l);
r = last_of_height(1, r);
cout << r - l + 1 << endl;
}
}
cout << flush;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
192 ms |
15948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
596 KB |
Output is correct |
| 2 |
Correct |
6 ms |
724 KB |
Output is correct |
| 3 |
Correct |
6 ms |
584 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Correct |
134 ms |
2180 KB |
Output is correct |
| 6 |
Incorrect |
188 ms |
2624 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
160 ms |
2624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
174 ms |
2704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
12140 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
201 ms |
13616 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
205 ms |
14500 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
16140 KB |
Output is correct |
| 2 |
Incorrect |
229 ms |
14200 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
15668 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
237 ms |
18880 KB |
Output is correct |
