Submission #1102813

#TimeUsernameProblemLanguageResultExecution timeMemory
1102813blackslexGrowing Trees (BOI11_grow)C++17
0 / 100
1032 ms2128 KiB
#include<bits/stdc++.h> #define lsb(x) (x &(-x)) using namespace std; const int N = 1e5 + 5, K = 19; int n, q, x, y, fwk[N]; char c; void upd (int idx, int val) { for (; idx <= n; idx += lsb(idx)) fwk[idx] += val; } int qr (int idx) { int res = 0; for (; idx; idx -= lsb(idx)) res += fwk[idx]; return res; } int lb (int val) { int idx = 0, res = 0; for (int i = K - 1; i >= 0; i--) { if (idx + (1 << i) <= n && res + fwk[idx + (1 << i)] < val) res += fwk[idx += (1 << i)]; } return ++idx; } int ub (int val) { int idx = 0, res = 0; for (int i = K - 1; i >= 0; i--) { if (idx + (1 << i) <= n && res + fwk[idx + (1 << i)] <= val) res += fwk[idx += (1 << i)]; } return idx; } int main() { scanf("%d %d", &n, &q); vector<int> a(n + 5); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); sort(a.begin() + 1, a.begin() + n + 1); for (int i = 1; i <= n; i++) upd(i, a[i] - a[i - 1]); while (q--) { scanf(" %c %d %d", &c, &x, &y); if (c == 'F') { int k = lb(y); int cqr = qr(k + x - 1); int clb = lb(cqr), cub = ub(cqr); int al = clb - k; int req = x - al; upd(k, 1); upd(clb, -1); if (al < x) upd(cub - req + 1, 1), upd(cub + 1, -1); } else { int clb = lb(x), cub = ub(min(y, qr(n))); printf("%d\n", cub - clb + 1); } } }

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:39:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
      |                                  ~~~~~^~~~~~~~~~~~~
grow.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf(" %c %d %d", &c, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...