Submission #1215219

#TimeUsernameProblemLanguageResultExecution timeMemory
1215219vaneaGrowing Trees (BOI11_grow)C++20
100 / 100
72 ms1604 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mxN = 1e5+10; int bit[mxN], n; void add(int l, int r, int x) { for(; l <= n; l += (l & (-l))) bit[l] += x; for(++r; r <= n; r += (r & (-r))) bit[r] -= x; } int query(int x) { int sum = 0; for(; x >= 1; x -= (x & (-x))) sum += bit[x]; return sum; } int qry(int l1, int r1, auto f) { int l = l1, r = r1+1; while(l < r) { int mid = l + (r - l) / 2; if(f(mid)) r = mid; else l = mid+1; } return l; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int q; cin >> n >> q; vector<int> v(n+1); for(int i = 1; i <= n; i++) { cin >> v[i]; } sort(v.begin(), v.end()); for(int i = 1; i <= n; i++) add(i, i, v[i]); while(q--) { char flag; cin >> flag; if(flag == 'F') { int c, h; cin >> c >> h; int l = qry(1, n, [&](int x) {return query(x) >= h;}); if(l == n+1) continue; int r = l + c - 1; if(r >= n) { add(l, n, 1); continue; } int x = query(r); int l1 = qry(l, n, [&](int i) { return query(i) >= x;}); int r1 = qry(l1, n, [&](int i) {return query(i) > x;}) - 1; add(l, l1-1, 1); add(r1 - (c - (l1 - l)) + 1, r1, 1); } else { int mn, mx; cin >> mn >> mx; int l = qry(1, n, [&](int i) {return query(i) >= mn;}); int r = qry(1, n, [&](int i) {return query(i) > mx;}); cout << r-l << '\n'; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...