Submission #1217306

#TimeUsernameProblemLanguageResultExecution timeMemory
1217306reginoxMeteors (POI11_met)C++20
74 / 100
1687 ms44680 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define all(v) begin(v), end(v) #define pi pair<int, int> #define vi vector<int> using namespace std; struct Fenwick{ int n; vector<vector<ll>> t; Fenwick(int n = 0){ this->n = n; t.assign(n+1, vector<ll>(2, 0)); } void ass(int n){ this->n = n; t.assign(n+1, vector<ll>(2, 0)); } void upd(int tp, int id, ll x){ for(int i = id; i <= n; i+=i&(-i)) t[i][tp]+=x; } void add(int l, int r, ll x){ upd(0, l, x); upd(0, r+1, -x); upd(1, l, x*(l-1)); upd(1, r+1, -x*r); } ll sum(int tp, int id){ ll res = 0; for(int i = id; i > 0; i-=i&(-i)) res+=t[i][tp]; return res; } ll get(int x){ return sum(0, x)*(ll)x - sum(1, x); } ll query(int a, int b){ return get(b) - get(a-1); } }; int n, m, q; vector<pi> e; vector<vi> st; vector<ll> tar, ff; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; tar.resize(n); st.resize(n); for(int i = 0; i < m; i++){ int x; cin >> x; x--; st[x].push_back(i); } for(auto &x:tar) cin >> x; cin >> q; ff.resize(q); e.resize(q); for(int i = 0; i < q; i++){ cin >> e[i].first >> e[i].second >> ff[i]; e[i].first--; e[i].second--; } vi L(n, 0), R(n, q+1); vector<vi> c(q+1); Fenwick f(m); while(true){ bool has = false; for(int i = 0; i < n; i++){ if(L[i] < R[i]){ has = true; int mid = (L[i] + R[i])/2; c[mid].push_back(i); } } if(!has) break; for(int i = 0; i <= q; i++){ if(i > 0){ int l = e[i-1].first, r = e[i-1].second; if(l <= r){ f.add(l+1, r+1, ff[i-1]); } else{ f.add(l+1, m, ff[i-1]); f.add(1, r+1, ff[i-1]); } } // cerr << "dit\n"; for(auto x:c[i]){ ll su = 0; for(auto y:st[x]){ su += f.query(y+1, y+1); } if(su >= tar[x]) R[x] = i; else L[x] = i+1; } c[i].clear(); } f.ass(m); } for(int i = 0; i < n; i++){ if(L[i] > q) cout << "NIE\n"; else cout << L[i] << "\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...