Submission #728393

#TimeUsernameProblemLanguageResultExecution timeMemory
728393piOOEFood Court (JOI21_foodcourt)C++17
20 / 100
1074 ms41324 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; namespace SegmentTree { struct Info { ll sum = 0, mn = 0, mn2 = 3e18; int cntmn = 0, len = 0; }; Info operator+(const Info &a, const Info &b) { Info res{}; res.sum = a.sum + b.sum, res.len = a.len + b.len; res.mn = min(a.mn, b.mn); res.mn2 = min(a.mn == res.mn ? a.mn2 : a.mn, b.mn == res.mn ? b.mn2 : b.mn); res.cntmn = (a.mn == res.mn) * a.cntmn + (b.mn == res.mn) * b.cntmn; return res; } vector<Info> t; vector<ll> tag; int sz = 1; void pull(int x) { t[x] = t[x << 1] + t[x << 1 | 1]; } void applyAdd(int x, ll tg) { tag[x] += tg; t[x].sum += t[x].len * tg; t[x].mn += tg, t[x].mn2 += tg; } void applyMin(int x, ll d) { if (t[x].mn < d) { assert(t[x].mn2 > d); t[x].sum += t[x].cntmn * (d - t[x].mn); t[x].mn = d; } } void push(int x) { if (tag[x]) { applyAdd(x << 1, tag[x]); applyAdd(x << 1 | 1, tag[x]); tag[x] = 0; } applyMin(x << 1, t[x].mn); applyMin(x << 1 | 1, t[x].mn); } void init(int n) { sz = 1 << __lg(n) + !!(n & (n - 1)); t.assign(sz << 1, {}), tag.assign(sz << 1, {}); for (int i = 0; i < n; ++i) { t[i + sz].cntmn = t[i + sz].len = 1; } for (int i = sz - 1; i > 0; --i) { pull(i); } } void rangeAdd(int l, int r, ll d, int x, int lx, int rx) { if (lx >= r || l >= rx) { return; } if (l <= lx && rx <= r) { return applyAdd(x, d); } push(x); int mid = (lx + rx) >> 1; rangeAdd(l, r, d, x << 1, lx, mid), rangeAdd(l, r, d, x << 1 | 1, mid, rx); pull(x); } void rangeSetMax(int l, int r, ll d, int x = 1, int lx = 0, int rx = sz) { if (l >= rx || lx >= r || t[x].mn >= d) { return; } if (l <= lx && rx <= r && t[x].mn2 > d) { return applyMin(x, d); } push(x); int mid = lx + rx >> 1; rangeSetMax(l, r, d, x << 1, lx, mid), rangeSetMax(l, r, d, x << 1 | 1, mid, rx); pull(x); } void rangeAdd(int l, int r, ll d) { rangeAdd(l, r, d, 1, 0, sz); rangeSetMax(l, r, 0); } ll sum(int i, int x = 1, int lx = 0, int rx = sz) { while (x < sz) { push(x); int mid = lx + rx >> 1; if (i < mid) { x = x << 1; rx = mid; } else { x = x << 1 | 1; lx = mid; } } return t[x].sum; } } template<typename T> struct Fenwick { int n; vector<T> a; Fenwick() = default; explicit Fenwick(int n) : n(n), a(n + 1) {} void modify(int x, T v) { for (int i = x + 1; i <= n; i += i & -i) { a[i] += v; } } void modify(int l, int r, T v) { if (l >= r) return; modify(l, v), modify(r, -v); } T sum(int x) { T ans = 0; for (int i = x + 1; i > 0; i -= i & -i) { ans += a[i]; } return ans; } }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin >> n >> m >> q; struct Query { int t, l, r, c; ll k; }; vector<Query> queries(q); vector<vector<int>> que(q); vector<int> L(q, -1), R(q, -1); vector<ll> aim(q); Fenwick<ll> fn(n); SegmentTree::init(n); for (int i = 0; i < q; ++i) { cin >> queries[i].t; if (queries[i].t == 1) { cin >> queries[i].l >> queries[i].r >> queries[i].c >> queries[i].k; } else if (queries[i].t == 2) { cin >> queries[i].l >> queries[i].r >> queries[i].k; } else { cin >> queries[i].l >> queries[i].k; } queries[i].l -= 1; if (queries[i].t == 1) { SegmentTree::rangeAdd(queries[i].l, queries[i].r, queries[i].k); } else if (queries[i].t == 2) { SegmentTree::rangeAdd(queries[i].l, queries[i].r, -queries[i].k); fn.modify(queries[i].l, queries[i].r, queries[i].k); } else { ll s = fn.sum(queries[i].l); ll have = SegmentTree::sum(queries[i].l) + s; ll need = queries[i].k + s; if (have >= need) { R[i] = i; aim[i] = need; } else { R[i] = -1; } } } int cnt = 0; while (true) { assert(++cnt <= 30); for (int i = 0; i < q; ++i) { que[i].clear(); } bool found = false; for (int i = 0; i < q; ++i) { if (L[i] + 1 < R[i]) { found = true; que[L[i] + R[i] >> 1].push_back(i); } } if (!found) { break; } fn = Fenwick<ll>(n); SegmentTree::init(n); for (int i = 0; i < q; ++i) { if (queries[i].t == 1) { SegmentTree::rangeAdd(queries[i].l, queries[i].r, queries[i].k); } else if (queries[i].t == 2) { SegmentTree::rangeAdd(queries[i].l, queries[i].r, -queries[i].k); fn.modify(queries[i].l, queries[i].r, queries[i].k); } for (int j : que[i]) { ll need = aim[j]; ll have = SegmentTree::sum(queries[j].l) + fn.sum(queries[j].l); if (have >= need) { R[j] = i; } else { L[j] = i; } } } } for (int i = 0; i < q; ++i) { if (queries[i].t == 3) { if (R[i] == -1) { cout << 0 << '\n'; } else { cout << queries[R[i]].c << '\n'; } } } return 0; }

Compilation message (stderr)

foodcourt.cpp: In function 'void SegmentTree::init(int)':
foodcourt.cpp:54:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   54 |         sz = 1 << __lg(n) + !!(n & (n - 1));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'void SegmentTree::rangeSetMax(int, int, ll, int, int, int)':
foodcourt.cpp:86:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
foodcourt.cpp: In function 'll SegmentTree::sum(int, int, int, int)':
foodcourt.cpp:99:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |             int mid = lx + rx >> 1;
      |                       ~~~^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:206:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  206 |                 que[L[i] + R[i] >> 1].push_back(i);
#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...