Submission #955363

#TimeUsernameProblemLanguageResultExecution timeMemory
955363Der_VlaposFood Court (JOI21_foodcourt)C++17
100 / 100
585 ms54148 KiB
// #pragma GCC target("avx2") // #pragma GCC optimize("O3") // #include <x86intrin.h> #include <bits/stdc++.h> #include <chrono> #include <random> // @author: Vlapos namespace operators { template <typename T1, typename T2> std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x) { in >> x.first >> x.second; return in; } template <typename T1, typename T2> std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x) { out << x.first << " " << x.second; return out; } template <typename T1> std::istream &operator>>(std::istream &in, std::vector<T1> &x) { for (auto &i : x) in >> i; return in; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::vector<T1> &x) { for (auto &i : x) out << i << " "; return out; } template <typename T1> std::ostream &operator<<(std::ostream &out, std::set<T1> &x) { for (auto &i : x) out << i << " "; return out; } } // name spaces using namespace std; using namespace operators; // end of name spaces // defines #define ll long long #define ull unsigned long long #define pb push_back #define mp make_pair #define pii pair<int, int> #define pll pair<ll, ll> #define f first #define s second #define uint unsigned int #define all(vc) vc.begin(), vc.end() // end of defines // usefull stuff void boost() { ios_base ::sync_with_stdio(false); cin.tie(0); cout.tie(0); } inline int getbit(int &x, int &bt) { return (x >> bt) & 1; } const int dx4[4] = {-1, 0, 0, 1}; const int dy4[4] = {0, -1, 1, 0}; const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1}; const ll INF = (1e17) + 500; const int BIG = (1e9) * 2 + 100; const int MAXN = (1e5) + 5; const int MOD7 = (1e9) + 7; const int MOD9 = (1e9) + 9; const uint MODFFT = 998244353; #define int ll struct segTree { struct Node { int mx = 0, op = 0; }; vector<Node> tree; int sz = 0; void init(int n) { sz = 1; while (sz < n) sz *= 2; tree.resize(2 * sz); } void upd(int v, int val) { tree[v].op += val; tree[v].mx += val; } void push(int v, int lv, int rv) { if (rv - lv == 1 or tree[v].op == 0) return; upd(v * 2 + 1, tree[v].op); upd(v * 2 + 2, tree[v].op); tree[v].op = 0; } void updSeg(int l, int r, int val, int v, int lv, int rv) { push(v, lv, rv); if (l <= lv and rv <= r) { upd(v, val); return; } if (rv <= l or r <= lv) return; int m = (lv + rv) >> 1; updSeg(l, r, val, v * 2 + 1, lv, m); updSeg(l, r, val, v * 2 + 2, m, rv); tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx); } void updSeg(int l, int r, int val) { updSeg(l, r, val, 0, 0, sz); } int getPos(int pos, int v, int lv, int rv) { push(v, lv, rv); if (rv - lv == 1) return tree[v].mx; int m = (lv + rv) >> 1; if (pos < m) return getPos(pos, v * 2 + 1, lv, m); return getPos(pos, v * 2 + 2, m, rv); } int getPos(int pos) { return getPos(pos, 0, 0, sz); } int getGoodPos(int v, int lv, int rv) { push(v, lv, rv); if (rv - lv == 1) return lv; int m = (lv + rv) >> 1; if (tree[v * 2 + 1].mx >= 0) return getGoodPos(v * 2 + 1, lv, m); return getGoodPos(v * 2 + 2, m, rv); } int getGoodPos() { return getGoodPos(0, 0, sz); } }; struct segTreeBF { struct Node { int add = 0, del = 0; }; vector<Node> tree; int sz = 0; void init(int n) { sz = 1; while (sz < n) sz *= 2; tree.resize(2 * sz); } void upd(int v, int val) { if (tree[v].add + val >= 0) tree[v].add = tree[v].add + val; else { tree[v].del += tree[v].add + val; tree[v].add = 0; } } void push(int v, int lv, int rv) { if (rv - lv == 1 or (tree[v].add == 0 and tree[v].del == 0)) return; upd(v * 2 + 1, tree[v].del); upd(v * 2 + 1, tree[v].add); upd(v * 2 + 2, tree[v].del); upd(v * 2 + 2, tree[v].add); tree[v].add = tree[v].del = 0; } void updSeg(int l, int r, int val, int v, int lv, int rv) { push(v, lv, rv); if (l <= lv and rv <= r) { upd(v, val); return; } if (rv <= l or r <= lv) return; int m = (lv + rv) >> 1; updSeg(l, r, val, v * 2 + 1, lv, m); updSeg(l, r, val, v * 2 + 2, m, rv); } void updSeg(int l, int r, int val) { updSeg(l, r, val, 0, 0, sz); } int getPos(int pos, int v, int lv, int rv) { push(v, lv, rv); if (rv - lv == 1) { return tree[v].add; } int m = (lv + rv) >> 1; if (pos < m) return getPos(pos, v * 2 + 1, lv, m); return getPos(pos, v * 2 + 2, m, rv); } int getPos(int pos) { return getPos(pos, 0, 0, sz); } }; struct test { void solve(int testcase) { boost(); int n, m, q; cin >> n >> m >> q; int cntA = 0; vector<vector<pair<int, int>>> ops(n); vector<pair<pii, pii>> updates; segTreeBF bf1, bf2; vector<int> ans; bf1.init(n); bf2.init(n); for (int i = 0; i < q; ++i) { int tp; cin >> tp; if (tp == 1) { int l, r, c, k; cin >> l >> r >> c >> k; --l; updates.pb({{l, r}, {c, k}}); bf1.updSeg(l, r, k); bf2.updSeg(l, r, k); } else if (tp == 2) { int l, r, k; cin >> l >> r >> k; --l; bf2.updSeg(l, r, -k); } else { int p, val; cin >> p >> val; --p; int cntLeave = bf1.getPos(p) - bf2.getPos(p); ans.pb(0); if (bf2.getPos(p) >= val) ops[p].pb({cntLeave + val, cntA}); cntA++; } } for (int i = 0; i < n; ++i) ops[i].pb({INF, BIG}); segTree res; res.init(n + 1); vector<int> prev(n + 1); for (int i = 0; i < n; ++i) { sort(all(ops[i])); reverse(all(ops[i])); int val = ops[i].back().f; res.updSeg(i, i + 1, -val); prev[i] = -val; } for (auto [seg, vals] : updates) { res.updSeg(seg.f, seg.s, vals.s); int p = res.getGoodPos(); while (p < n) { ans[ops[p].back().s] = vals.f; ops[p].pop_back(); int val = ops[p].back().f; res.updSeg(p, p + 1, -prev[p] - val); prev[p] = -val; p = res.getGoodPos(); } } for (auto el : ans) cout << el << '\n'; } }; main() { boost(); int q = 1; // cin >> q; for (int i = 0; i < q; i++) { test t; t.solve(i); } return 0; } //[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]// // // // Coded by Der_Vlἀpos // // // //[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//

Compilation message (stderr)

foodcourt.cpp:340:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  340 | main()
      | ^~~~
#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...