Submission #967425

#TimeUsernameProblemLanguageResultExecution timeMemory
96742512345678Meteors (POI11_met)C++17
100 / 100
1676 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int nx=4e5+5; int n, m, p[nx], q, l[nx], r[nx], ul, ur, a, cnt=19, t[nx]; vector<int> d[nx], qrs[nx]; vector<pair<int, pair<int, int>>> k; struct fenwick { ll d[nx]; void update(int i, int vl) { while (i<nx) d[i]+=vl, i+=(i&-i); } ll query(int i) { ll res=0; while (i>0) res+=d[i], i-=(i&-i); return res; } } f; int main() { cin.tie(NULL)->sync_with_stdio(false); cin>>n>>m; for (int i=1; i<=m; i++) cin>>p[i], d[p[i]].push_back(i); for (int i=1; i<=n; i++) cin>>t[i]; cin>>q; for (int i=0; i<q; i++) cin>>ul>>ur>>a, k.push_back({a, {ul, ur}}); for (int i=1; i<=n; i++) l[i]=1, r[i]=q+1; while (cnt--) { for (int i=1; i<=n; i++) if (l[i]!=r[i]) qrs[(l[i]+r[i])/2].push_back(i); for (int i=1; i<=q+1; i++) { if (i==q+1) continue; int x=k[i-1].second.first, y=k[i-1].second.second, z=k[i-1].first; if (x<=y) f.update(x, z), f.update(y+1, -z); else f.update(1, z), f.update(y+1, -z), f.update(x, z), f.update(m+1, -z); //cout<<"fenwick "<<i<<':'; //for (int j=1; j<=m; j++) cout<<f.query(j)<<' '; //cout<<'\n'; for (auto idx:qrs[i]) { ll sm=0; for (auto id:d[idx]) sm+=f.query(id), sm=min(sm, (ll)t[idx]+1); //cout<<"debug "<<cnt<<' '<<idx<<' '<<sm<<'\n'; if (sm>=t[idx]) r[idx]=i; else l[idx]=i+1; } qrs[i].clear(); } for (int i=1; i<=m+1; i++) f.d[i]=0; } for (int i=1; i<=n; i++) { if (l[i]>q) cout<<"NIE\n"; else cout<<l[i]<<'\n'; } }
#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...