Submission #762283

#TimeUsernameProblemLanguageResultExecution timeMemory
762283otariusGrowing Trees (BOI11_grow)C++17
0 / 100
323 ms3244 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define sc second #define pb push_back #define ll long long #define pll pair<ll, ll> #define pii pair <int, int> #define ull unsigned long long // #define int long long // #define int unsigned long long const ll inf = 1e18 + 7; const ll weirdMod = 998244353; int t[400040], lazy[400040], n, m; void prop(int v, int tl, int tr) { t[v] += lazy[v] * (tr - tl + 1); if (tl != tr) { lazy[2 * v] += lazy[v]; lazy[2 * v + 1] += lazy[v]; } lazy[v] = 0; } void set_val(int v, int tl, int tr, int pos, int val) { if (tl == tr) { t[v] = val; return; } int tm = (tl + tr) / 2; if (pos <= tm) set_val(2 * v, tl, tm, pos, val); else set_val(2 * v + 1, tm + 1, tr, pos, val); } int get_val(int v, int tl, int tr, int pos) { if (lazy[v]) prop(v, tl, tr); if (tl == tr) return t[v]; int tm = (tl + tr) / 2; if (pos <= tm) return get_val(2 * v, tl, tm, pos); else return get_val(2 * v + 1, tm + 1, tr, pos); } void add_one(int v, int tl, int tr, int l, int r) { if (lazy[v]) prop(v, tl, tr); if (tr < l || tl > r) return; if (l <= tl && tr <= r) { t[v] += tr - tl + 1; if (tl != tr) { lazy[2 * v]++; lazy[2 * v + 1]++; } return; } int tm = (tl + tr) / 2; add_one(2 * v, tl, tm, l, min(r, tm)); add_one(2 * v + 1, tm + 1, tr, max(l, tm + 1), r); } void upd_query(int c, int h) { int l = 1, r = n, m; while (l < r) { m = (l + r) / 2; if (get_val(1, 1, n, m) < h) l = m + 1; else r = m; } while (l - 1 > 0 && get_val(1, 1, n, l - 1) >= h) l--; if (get_val(1, 1, n, l) < h) return; int lst = min(n, l + c - 1), bad_num = get_val(1, 1, n, lst); if (get_val(1, 1, n, l) == bad_num) { add_one(1, 1, n, max(l, lst - c + 1), lst); return; } int pos = l; l = 1; r = n; while (l < r) { m = (l + r) / 2; if (get_val(1, 1, n, m) < bad_num) l = m + 1; else r = m; } while (l - 1 > 0 && get_val(1, 1, n, l - 1) >= bad_num) l--; add_one(1, 1, n, pos, l - 1); c -= l - pos; int bad_num_pos = l; l = 1; r = n; while (l < r) { m = (l + r) / 2; if (get_val(1, 1, n, m) < bad_num + 1) l = m + 1; else r = m; } while (l - 1 > 0 && get_val(1, 1, n, l - 1) > bad_num) l--; l--; add_one(1, 1, n, max(bad_num_pos, l - c + 1), l); //for (int i = 1; i <= n; i++) cout << get_val(1, 1, n, i) << ' '; //cout << '\n'; } void ans_query(int a, int b) { int l = 1, r = n, m; while (l < r) { m = (l + r) / 2; if (get_val(1, 1, n, m) < a) l = m + 1; else r = m; } while (l - 1 > 0 && get_val(1, 1, n, l - 1) >= a) l--; if (get_val(1, 1, n, l) < a) { cout << 0 << '\n'; return; } int pos = l; l = 1; r = n; m; while (l < r) { m = (l + r) / 2; if (get_val(1, 1, n, m) < b) l = m + 1; else r = m; } while (l - 1 > 0 && get_val(1, 1, n, l - 1) >= b) l--; cout << l - pos + 1 << '\n'; } void solve() { cin >> n >> m; vector<int> vec(n); for (auto &v : vec) cin >> v; sort(vec.begin(), vec.end()); for (int i = 1; i <= n; i++) set_val(1, 1, n, i, vec[i - 1]); char v; int l, r; for (int i = 1; i <= m; i++) { cin >> v >> l >> r; if (v == 'F') upd_query(l, r); else ans_query(l, r); } } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

grow.cpp: In function 'void ans_query(int, int)':
grow.cpp:98:19: warning: statement has no effect [-Wunused-value]
   98 |     l = 1; r = n; m;
      |                   ^
#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...