Submission #532679

#TimeUsernameProblemLanguageResultExecution timeMemory
532679Ai7081Meteors (POI11_met)C++17
0 / 100
97 ms35632 KiB
#include <bits/stdc++.h> using namespace std; #define long long long const long N = 300005; struct tree{ long val, lazy; int l, r; }; long n, m, q; int want[N]; vector<int> own[N], roots; vector<tree> t; int build(int tl, int tr) { int now = t.size(); t.push_back({0, 0, -1, -1}); if (tl == tr) return now; int tm = (tl+tr)/2; t[now].l = build(tl, tm); t[now].r = build(tm+1, tr); return now; } void push(int v, int tl, int tr) { if (t[v].lazy && tl != tr) { int tm = (tl+tr)/2; int left = t.size(), right = left + 1; t.push_back(t[t[v].l]); t.push_back(t[t[v].r]); t[left].lazy += t[v].lazy; t[right].lazy += t[v].lazy; t[left].val += t[v].lazy * (tm-tl+1); t[right].val += t[v].lazy * (tr-tm); t[v].lazy = 0; t[v].l = left; t[v].r = right; } return; } int update(int v, int tl, int tr, int l, int r, long val) { if (tr < l || tl > r) return -1; int now = t.size(); t.push_back(t[v]); // cout << "update " << v << ' ' << tl << ' ' << tr << endl; if (l <= tl && tr <= r) { t[now].val += val * (tr-tl+1); t[now].lazy += val; return now; } push(now, tl, tr); int tm = (tl+tr)/2; int left = update(t[now].l , tl, tm, l, r, val); int right = update(t[now].r, tm+1, tr, l, r, val); if (left != -1) t[now].l = left; if (right != -1) t[now].r = right; return now; } long find_val(int v, int tl, int tr, int pos) { if (tl == tr) return t[v].val; push(v, tl, tr); int tm = (tl+tr)/2; if (pos <= tm) return find_val(t[v].l, tl, tm, pos); else return find_val(t[v].r, tm+1, tr, pos); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for (int i=1; i<=m; i++) { long x; cin >> x; own[x].push_back(i); } for (int i=1; i<=n; i++) cin >> want[i]; roots.push_back(build(1, n)); // cout << "build success" << endl; cin >> q; for (int i=1; i<=q; i++) { int l, r; long val; cin >> l >> r >> val; if (l <= r) roots.push_back(update(roots[roots.size()-1], 1, m, l, r, val)); else { int now = update(roots[roots.size()-1], 1, m, 1, r, val); roots.push_back(update(now, 1, m, l, m, val)); } } // cout << "persist success" << endl; for (int i=1; i<=n; i++) { int l = 1, r = q+1; while (l < r) { long sum = 0; int mid = (l+r)/2; // cout << "owner " << i << " : " << l << ' ' << mid << ' ' << r << endl; for (auto it : own[i]) { sum += find_val(roots[mid], 1, m, it); } if (want[i] <= sum) r = mid; else l = mid+1; } // cout << "ans : l " << l << " r " << r << " : "; if (r == q+1) cout << "NIE" << endl; else cout << l << endl; } return 0; }
#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...