Submission #926315

#TimeUsernameProblemLanguageResultExecution timeMemory
926315VMaksimoski008Meteors (POI11_met)C++14
74 / 100
136 ms65536 KiB
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() using namespace std; using ll = long long; void setIO() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } struct BIT { int n, n2; vector<ll> tree, val; void config(int _n) { n = _n + 10; n2 = _n; tree.resize(_n+60); val.resize(_n+60); } void add(int p, int v) { val[p] += v; for(p++; p<n; p+=p&-p) tree[p] += v; } ll query(int p) { ll ans = 0; for(p++; p>0; p-=p&-p) ans += tree[p]; return ans; } ll sum(int l, int r) { return query(r) - query(l-1); } void set(int p, int v) { add(p, v - val[p]); } void clear() { for(ll &x : tree) x = 0; for(ll &x : val) x = 0; } }; struct Query { int l, r, x; }; int32_t main() { setIO(); int n, m; cin >> n >> m; vector<vector<int> > owner(n+5); for(int i=1; i<=m; i++) { int x; cin >> x; owner[x].push_back(i); } vector<ll> req(n+5); for(int i=1; i<=n; i++) cin >> req[i]; int k; cin >> k; vector<Query> qus(k+5); for(int i=1; i<=k; i++) cin >> qus[i].l >> qus[i].r >> qus[i].x; vector<int> L(n+5, 1), R(n+5, k+1); bool changed = true; BIT bit; bit.config(m+1); vector<stack<int> > to_check(k+5); Query q; while(changed) { changed = false; bit.clear(); for(int i=1; i<=n; i++) if(L[i] != R[i]) to_check[(L[i]+R[i])/2].push(i); for(int it=1; it<=k; it++) { q = qus[it]; if(q.l <= q.r) { bit.add(q.l, q.x); bit.add(q.r+1, -q.x); } else { bit.add(q.l, q.x); bit.add(m+1, -q.x); bit.add(1, q.x); bit.add(q.r+1, -q.x); } while(!to_check[it].empty()) { changed = true; int u = to_check[it].top(); to_check[it].pop(); ll total = 0; for(int &x : owner[u]) { total += bit.query(x); if(total > req[u]) break; } if(total >= req[u]) R[u] = it; else L[u] = it + 1; } } } for(int i=1; i<=n; i++) { if(L[i] <= k) cout << L[i] << '\n'; else cout << "NIE\n"; } 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...