Submission #728521

#TimeUsernameProblemLanguageResultExecution timeMemory
728521piOOEFood Court (JOI21_foodcourt)C++17
100 / 100
529 ms44420 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; namespace SegmentTree { constexpr int N_ = 1 << 19; pair<ll, ll> t[N_]; // f(x) = max(0, x - t[i].first) + t[i].second int sz = 1; void init(int n) { sz = 1 << __lg(n) + !!(n & (n - 1)); } void apply(int x, pair<ll, ll> d) { if (t[x].second >= d.first) { t[x] = {t[x].first, t[x].second - d.first + d.second}; } else { t[x] = {t[x].first + d.first - t[x].second, d.second}; } } void push(int x) { if (t[x].first || t[x].second) { apply(x << 1, t[x]), apply(x << 1 | 1, t[x]); t[x] = {}; } } void rangeApply(int l, int r, pair<ll, ll> a, int x = 1, int lx = 0, int rx = sz) { if (l >= rx || lx >= r) { return; } if (l <= lx && rx <= r) { return apply(x, a); } push(x); int mid = lx + rx >> 1; rangeApply(l, r, a, x << 1, lx, mid), rangeApply(l, r, a, x << 1 | 1, mid, rx); } ll query(int x) { ll d = 0; for (x += sz; x >= 1; x >>= 1) { d = max(0LL, d - t[x].first) + t[x].second; } return d; } } namespace SegmentTreeMin { constexpr int N_ = 1 << 19; pair<ll, int> t[N_]; // f(x) = max(0, x - t[i].first) + t[i].second ll tag[N_]; int sz = 1; void init(int n) { sz = 1 << __lg(n) + !!(n & (n - 1)); for (int i = 0; i < sz; ++i) { t[i + sz] = {i < n ? 0 : 3e18, i}; } for (int i = sz - 1; i > 0; --i) { t[i] = min(t[i << 1], t[i << 1 | 1]); } } void apply(int x, ll d) { tag[x] += d, t[x].first += d; } void rangeAdd(int l, int r, ll a, int x = 1, int lx = 0, int rx = sz) { if (l >= rx || lx >= r) { return; } if (l <= lx && rx <= r) { return apply(x, a); } int mid = lx + rx >> 1; rangeAdd(l, r, a, x << 1, lx, mid), rangeAdd(l, r, a, x << 1 | 1, mid, rx); t[x] = min(t[x << 1], t[x << 1 | 1]); t[x].first += tag[x]; } } 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; } }; constexpr int N = 2.5e5 + 10; vector<pair<ll, int>> que[N]; int pnt[N]; 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); Fenwick<ll> fn(n), fnAdd(n); SegmentTree::init(n); SegmentTreeMin::init(n); vector<ll> ans(q); 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::rangeApply(queries[i].l, queries[i].r, {0, queries[i].k}); fnAdd.modify(queries[i].l, queries[i].r, queries[i].k); } else if (queries[i].t == 2) { SegmentTree::rangeApply(queries[i].l, queries[i].r, {queries[i].k, 0}); fn.modify(queries[i].l, queries[i].r, queries[i].k); } else { ll s = fn.sum(queries[i].l); ll have = SegmentTree::query(queries[i].l) + s; ll need = queries[i].k + s; if (have >= need) { que[queries[i].l].emplace_back(fnAdd.sum(queries[i].l) - (have - s - queries[i].k), i); } } } auto relax = [&](int i) { if (pnt[i] == que[i].size()) { SegmentTreeMin::rangeAdd(i, i + 1, 3e18); } else { SegmentTreeMin::rangeAdd(i, i + 1, que[i][pnt[i]].first - (pnt[i] == 0 ? 0 : que[i][pnt[i] - 1].first)); } }; for (int i = 0; i < n; ++i) { sort(que[i].begin(), que[i].end()); relax(i); } for (int i = 0; i < q; ++i) { if (queries[i].t == 1) { SegmentTreeMin::rangeAdd(queries[i].l, queries[i].r, -queries[i].k); } while (SegmentTreeMin::t[1].first <= 0) { int j = SegmentTreeMin::t[1].second; ans[que[j][pnt[j]].second] = queries[i].c; ++pnt[j]; relax(j); } } for (int i = 0; i < q; ++i) { if (queries[i].t == 3) { cout << ans[i] << '\n'; } } return 0; }

Compilation message (stderr)

foodcourt.cpp: In function 'void SegmentTree::init(int)':
foodcourt.cpp:15:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   15 |         sz = 1 << __lg(n) + !!(n & (n - 1));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'void SegmentTree::rangeApply(int, int, std::pair<long long int, long long int>, int, int, int)':
foodcourt.cpp:41:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
foodcourt.cpp: In function 'void SegmentTreeMin::init(int)':
foodcourt.cpp:62:27: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   62 |         sz = 1 << __lg(n) + !!(n & (n - 1));
      |                   ~~~~~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp: In function 'void SegmentTreeMin::rangeAdd(int, int, ll, int, int, int)':
foodcourt.cpp:82:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
foodcourt.cpp: In lambda function:
foodcourt.cpp:172:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  172 |         if (pnt[i] == que[i].size()) {
      |             ~~~~~~~^~~~~~~~~~~~~~~~
#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...