Submission #762270

#TimeUsernameProblemLanguageResultExecution timeMemory
762270otariusGrowing Trees (BOI11_grow)C++17
0 / 100
390 ms3276 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); t[v] = t[2 * v] + t[2 * v + 1]; } 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 (l > tr || r < tl) 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); t[v] = t[2 * v] + t[2 * v + 1]; } 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 pos = l, lst = min(n, l + c - 1); int bad_num = get_val(1, 1, n, lst), bad_num_pos = lst; if (bad_num == get_val(1, 1, n, pos)) { add_one(1, 1, n, max(l, lst - c + 1), lst); return; } l = pos; 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) >= bad_num) l--; c -= l - pos + 1; int good_pos = l; l++; 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) > bad_num) l--; add_one(1, 1, n, max(bad_num_pos, l - c + 1), l); add_one(1, 1, n, pos, good_pos); } 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; 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--; if (get_val(1, 1, n, l) < b) cout << n - pos + 1 << '\n'; else 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; }
#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...