Submission #1000846

#TimeUsernameProblemLanguageResultExecution timeMemory
1000846wangziyanmoMeteors (POI11_met)C++14
74 / 100
503 ms65536 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mxn=300000; vector<int> belong[mxn+10]; int tar[mxn+10]; int l[mxn+10],r[mxn+10],mid[mxn+10],num[mxn+10]; int tree[mxn+10]; struct node{ int l1,r1,l2,r2,x,time; } event[mxn]; bool cmp(node a,node b){ if (a.time<b.time || (a.time==b.time && a.x>b.x)) return true; return false; } bool finished(int q){ for (int i=1;i<=q;i++) if (l[i]!=r[i]) return 0; return 1; } void add(int x,int num){ if (x>mxn) return; while (x<=mxn){ tree[x]+=num; x+=x&(-x); } } int que(int x){ int ans=0; while (x>0){ ans+=tree[x]; x-=x&(-x); } return ans; } signed main(){ int n,m;cin>>n>>m; for (int i=1;i<=m;i++){ int x;cin>>x; belong[x].push_back(i); } for (int i=1;i<=n;i++){ cin>>tar[i]; } int q;cin>>q; for (int i=1;i<=n;i++) l[i]=1,r[i]=q+1; for (int i=1;i<=q;i++){ int l,r,x;cin>>l>>r>>x; if (r<l){ event[i]={l,m,1,r,x,i}; } else event[i]={l,r,-1,-1,x,i}; } event[q+1]={1,n,-1,-1,(int)1e9,q+1}; while (!finished(n)){ for (int i=1;i<=mxn+5;i++){ num[i]=tree[i]=0; } for (int i=1;i<=n;i++) mid[i]=l[i]+(r[i]-l[i])/2; vector<node> qu; for (int i=1;i<=n;i++){ qu.push_back({-1,-1,-1,-1,-i,mid[i]}); } for (int i=1;i<=q;i++) qu.push_back({event[i]}); sort(qu.begin(),qu.end(),cmp); for (auto x:qu){ if (x.x<0){ x.x*=-1; for (auto a:belong[x.x]){ num[x.x]+=que(a); } } else{ add(x.l1,x.x);add(x.r1+1,-x.x); if (x.l2>0){ add(x.l2,x.x);add(x.r2+1,-x.x); } } } for (int i=1;i<=n;i++){ if (l[i]==r[i]) continue; if (num[i]>=tar[i]){ r[i]=mid[i]; } else l[i]=mid[i]+1; } } for (int i=1;i<=n;i++){ if (l[i]==q+1) 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...