Submission #1097148

#TimeUsernameProblemLanguageResultExecution timeMemory
1097148anhthiGrowing Trees (BOI11_grow)C++14
0 / 100
21 ms8280 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define ll long long #define mp(x, y) make_pair(x, y) #define sz(v) ((int) (v).size()) #define all(v) (v).begin(), (v).end() #define MASK(i) (1LL << (i)) #define BIT(x, y) (((x) >> (y)) & 1) #define pb push_back #define max_rng *max_element #define min_rng *min_element #define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i) #define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i) #define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i) template <class X, class Y> inline bool maximize(X &x, Y y) { return (x < y ? x = y, true : false); } template <class X, class Y> inline bool minimize(X &x, Y y) { return (x > y ? x = y, true : false); } template <class X> inline void compress(vector<X> &a) { sort(all(a)); a.resize(unique(all(a)) - a.begin()); } int ctz(ll x) { return __builtin_ctzll(x); } int lg(ll x) { return 63 - __builtin_clzll(x); } int popcount(ll x) { return __builtin_popcount(x); } mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rand(ll l, ll r) { return l + abs((ll) rng()) % (r - l + 1); } const ll oo = (ll) 1e17; const int inf = (ll) 1e9 + 7, mod = (ll) 1e9 + 7; const int N = 2e6 + 5, M = 2e5 + 5, BASE = 307, LOG = 23; void add(int &x, int y) { x += y; if (x >= mod) x -= mod; } void sub(int &x, int y) { x -= y; if (x < 0) x += mod; } int n, m; int a[N]; struct Seg { int n; vector<int> st, lz; Seg(int n) : n(n) { st.resize(n << 2); lz.resize(n << 2); build(1, 1, n); } void build(int i, int l, int r) { if (l == r) return st[i] = a[l], void(); int m = (l + r) >> 1; build(2 * i, l, m); build(2 * i + 1, m + 1, r); st[i] = max(st[2 * i], st[2 * i + 1]); } void setNode(int i, int x) { st[i] += x; lz[i] += x; } void down(int i) { if (!lz[i]) return; setNode(2 * i, lz[i]); setNode(2 * i + 1, lz[i]); lz[i] = 0; return; } void upd(int i, int l, int r, int u, int v, int x) { if (l > v || r < u) return; if (l >= u && r <= v) return setNode(i, x); down(i); int m = (l + r) >> 1; upd(2 * i, l, m, u, v, x); upd(2 * i + 1, m + 1, r, u, v, x); st[i] = max(st[2 * i], st[2 * i + 1]); } void upd(int u, int v, int x) { if (u > v) return; return upd(1, 1, n, u, v, x); } int get(int p) { for (int i = 1, l = 1, r = n; l <= r; ) { down(i); if (l == r) return st[i]; int m = (l + r) >> 1; if (p > m) { l = m + 1; i = 2 * i + 1; } else { r = m; i = 2 * i; } } } int walk(int Max) { if (st[1] < Max) return n + 1; for (int i = 1, l = 1, r = n; l <= r; ) { down(i); if (l == r) return l; int m = (l + r) >> 1; if (st[2 * i] >= Max) { r = m; i = 2 * i; } else { l = m + 1; i = 2 * i + 1; } } } }; int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; rep(i, n) cin >> a[i]; sort(a + 1, a + 1 + n); Seg s(n); rep(_, m) { char type; cin >> type; if (type == 'F') { int c, h; cin >> c >> h; int pos = s.walk(h); // cout << pos << ' '; if (pos + c - 1 >= n) { s.upd(pos, n, +1); continue; } int lst = s.get(pos + c - 1); // cout << lst << '\n'; int first = max(s.walk(lst), pos); // cout << first << '\n'; s.upd(pos, first - 1, +1); int second = s.walk(lst + 1) - 1; // cout << second << '\n'; int cnt = pos + c - first; // cout << cnt << '\n'; s.upd(second - cnt + 1, second, +1); // cout << '\n'; // rep(i, n) cout << s.get(i) << ' '; // cout << '\n'; } else { int l, r; cin >> l >> r; int pos = s.walk(r); cout << pos - s.walk(l) + (pos <= n && s.get(pos) <= r) << '\n'; } } return 0; }

Compilation message (stderr)

grow.cpp: In member function 'int Seg::walk(int)':
grow.cpp:134:5: warning: control reaches end of non-void function [-Wreturn-type]
  134 |     }
      |     ^
grow.cpp: In member function 'int Seg::get(int)':
grow.cpp:117:5: warning: control reaches end of non-void function [-Wreturn-type]
  117 |     }
      |     ^
#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...