Submission #1213443

#TimeUsernameProblemLanguageResultExecution timeMemory
1213443orzorzorzGrowing Trees (BOI11_grow)C++20
0 / 100
67 ms2376 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int mxN = 1e5 + 1; ll bit[mxN + 1], a[mxN + 1]; int n, m; void upd(int pos, ll val) { for (; pos <= mxN; pos += pos & -pos) { bit[pos] += val; } } ll qry(int pos) { ll res = 0; for (; pos; pos -= pos & -pos) { res += bit[pos]; } return res; } int f(ll val) { int l = 1, r = n; while (l <= r) { int mid = (l + r) / 2; if (qry(mid) >= val) { r = mid - 1; } else { l = mid + 1; } } return l; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; } sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) { upd(i, a[i]); upd(i + 1, -a[i]); } for (int i = 0; i < m; i++) { char ty; cin >> ty; if (ty == 'F') { int c, h; cin >> c >> h; int left = f(h); if (left == n + 1) continue; int right = left + c - 1; if (right >= n) { upd(left, 1); upd(n + 1, -1); } else { upd(left, 1); upd(right + 1, -1); } } else { ll x, y; cin >> x >> y; int l = f(x), r = f(y + 1); if (l == n + 1) { cout << 0 << "\n"; } else { if (r == n + 1) r = n; cout << r - l + 1 << "\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...