| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1187401 | qrn | Growing Trees (BOI11_grow) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define SPEED \
ios_base::sync_with_stdio(0); \
cin.tie(NULL); \
cout.tie(NULL);
#define pb push_back
#define ins insert
#define fi first
#define se second
#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt int
const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e9;
const intt mxN = 2e5 + 5;
const intt L = 21;
struct nod {
intt sum, mx, mn;
};
nod seg[2 * mxN];
vector<intt> lazy(2 * mxN), A(mxN);
void build(intt node, intt l, intt r) {
if(l == r) {
seg[node].sum = seg[node].mx = seg[node].mn = A[l];
lazy[node] = -1;
return;
}
intt mid = (l + r) / 2;
build(node * 2, l, mid);
build(node * 2 + 1, mid + 1, r);
seg[node].sum = seg[node * 2].sum + seg[node * 2 + 1].sum;
seg[node].mx = max(seg[node * 2].mx, seg[node * 2 + 1].mx);
seg[node].mn = min(seg[node * 2].mn, seg[node * 2 + 1].mn);
}
void push(intt node, intt l, intt r){
if(lazy[node] == -1) return;
seg[node].sum += lazy[node];
seg[node].mn += lazy[node];
seg[node].mx += lazy[node];
if(l != r) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(intt node, intt l, intt r, intt ql, intt qr){
push(node, l, r);
if(ql > r || qr < l || ql > qr) return;
if(ql <= l && r <= qr) {
lazy[node]++;
push(node, l, r);
return;
}
intt mid = (l + r) / 2;
update(node * 2, l, mid, ql, qr);
update(node * 2 + 1, mid + 1, r, ql, qr);
seg[node].sum = seg[node * 2].sum + seg[node * 2 + 1].sum;
seg[node].mx = max(seg[node * 2].mx, seg[node * 2 + 1].mx);
seg[node].mn = min(seg[node * 2].mn, seg[node * 2 + 1].mn);
}
intt rett = -1;
intt get_cbii(intt node, intt l, intt r, intt val) {
push(node, l, r);
if(l == r) {
if(seg[node].mn > val) {
rett = l;
} else {
rett = -1;
}
return rett;
}
intt mid = (l + r) / 2;
if(seg[node * 2].mx <= val && seg[node * 2 + 1].mx <= val) {
rett = -1;
return rett;
}
if(seg[node * 2].mx > val) {
get_cbii(node * 2, l, mid, val);
} else {
get_cbii(node * 2 + 1, mid + 1, r, val);
}
}
void solve() {
intt N, Q;
cin >> N >> Q;
A.assign(N + 1, 0ll);
for(intt i = 1; i <= N; i++) {
cin >> A[i];
}
sort(ALL(A));
build(1, 1, N);
while(Q--) {
char c;
cin >> c;
if(c == 'F') {
intt H, C;
cin >> H >> C;
intt bbii = get_cbii(1, 1, N, H-1);
intt cbii = get_cbii(1, 1, N, H);
if(bbii == -1) {
rett = -1;
continue;
}
if(cbii - 1 >= 1 && A[cbii - 1] == H) cbii--;
intt equals = 0;
if(A[bbii] == H && A[cbii] == H) {
equals = cbii - bbii + 1;
} else if(A[bbii] == H) {
equals = cbii - bbii;
}
intt r = bbii + C - 1, boyukler = max(0ll, C - equals);
intt r_eq = r - boyukler;
intt l_eq = r_eq - (C - boyukler) + 1;
update(1, 1, N, l_eq, r_eq);
if(boyukler != 0) {
update(1, 1, N, r_eq + 1, r_eq + boyukler);
}
rett = -1;
} else {
intt l , r;
cin >> l >> r;
intt bbii = get_cbii(1, 1, N, l - 1);
intt cbii = get_cbii(1, 1, N, r);
if(bbii == -1) {
cout << 0 << endl;
rett = -1;
continue;
}
if(cbii == -1) {
cbii = N+1;
}
cout << cbii - bbii+1 << endl;
rett = -1;
}
}
}
signed main() {
SPEED;
intt tst = 1;
// cin >> tst;
while (tst--) {
solve();
}
}
/*
Bize lazimdi bir ededden ciddi boyuk olan ilk yeri tapaq, ciddi kicik olan ilk yeri tapaq
Bize lazimdi lazy update
Bu ikisini necese handle ede bilsek olacaq bomba -> elebil update edende bize lazimdiki H-a beraber olan axrinci ededleri edek, qalanlari ise eyni qalacaq
Bize lazimdi bizden boyuk nece dene *mecbur* update olunacaq ededlerin sayi -> max(0, C[i] - equals); equals = birinci yazdigimla tapa bilerik
*/