Submission #1065597

#TimeUsernameProblemLanguageResultExecution timeMemory
1065597phoenixFood Court (JOI21_foodcourt)C++17
0 / 100
114 ms40272 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = (1 << 18); #define cerr if (false) cout struct node { ll sum = 0; ll pre = 0; }; node tr[2 * N]; node combine(node a, node b) { node res; res.sum = a.sum + b.sum; res.pre = min(a.pre, a.sum + b.pre); return res; } void update(int pos, ll val) { cerr << "upd: " << pos << ' ' << val << '\n'; tr[pos += N] = {val, min(0ll, val)}; for (pos >>= 1; pos; pos >>= 1) tr[pos] = combine(tr[2 * pos], tr[2 * pos + 1]); cerr << "tree: " << tr[1].sum << ' ' << tr[1].pre << '\n'; } node get(int ql, int qr, int l = 0, int r = N - 1, int v = 1) { if (r < ql || l > qr) return node(); if (ql <= l && r <= qr) return tr[v]; int m = (l + r) / 2; return combine(get(ql, qr, l, m, 2 * v), get(ql, qr, m + 1, r, 2 * v + 1)); } ll cnt[2 * N]; void add(int v, ll a) { for (cnt[v += N] += a; v > 1; v >>= 1) cnt[v >> 1] = cnt[v] + cnt[v^1]; } ll count(int ql, int qr, int l = 0, int r = N - 1, int v = 1) { if (r < ql || l > qr) return 0; if (ql <= l && r <= qr) return cnt[v]; int m = (l + r) / 2; return count(ql, qr, l, m, 2 * v) + count(ql, qr, m + 1, r, 2 * v + 1); } int n, m, q; vector<pair<int, int>> join[N][2]; vector<pair<int, int>> leave[N][2]; vector<pair<int, int>> service[N]; map<int, int> timeToGroup; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> q; for (int t = 1; t <= q; t++) { int type; cin >> type; if (type == 1) { int l, r, k, c; cin >> l >> r >> c >> k; timeToGroup[t] = c; join[l][0].push_back({t, k}); join[r][1].push_back({t, k}); } if (type == 2) { int l, r, k; cin >> l >> r >> k; leave[l][0].push_back({t, k}); leave[r][1].push_back({t, k}); } if (type == 3) { int a, b; cin >> a >> b; service[a].push_back({t, b}); } } vector<int> res(q + 1, -2); for (int i = 1; i <= n; i++) { for (auto o : join[i][0]) { int t = o.first, k = o.second; update(t, +k); add(t, +k); } for (auto o : leave[i][0]) { int t = o.first, k = o.second; update(t, -k); } for (auto [t, b] : service[i]) { int num = get(1, t).sum - get(1, t).pre; // cerr << "service: " << t << ' ' << b << '\n'; // cerr << get(1, t).sum << '\n'; if (num < b) { res[t] = 0; continue; } int l = 0, r = t + 1; while (r - l > 1) { int m = (l + r) / 2; if (count(m, t) >= b) l = m; else r = m; } res[t] = timeToGroup[l]; } for (auto o : join[i][1]) { int t = o.first, k = o.second; update(t, 0); add(t, -k); } for (auto o : leave[i][1]) { int t = o.first, k = o.second; update(t, 0); } } for (int i = 1; i <= q; i++) { if (res[i] != -2) cout << res[i] << '\n'; } }

Compilation message (stderr)

foodcourt.cpp: In function 'int main()':
foodcourt.cpp:122:30: warning: unused variable 'k' [-Wunused-variable]
  122 |             int t = o.first, k = o.second;
      |                              ^
#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...