Submission #32126

#TimeUsernameProblemLanguageResultExecution timeMemory
32126dereotuMeteors (POI11_met)C++14
24 / 100
1586 ms38928 KiB
#include <bits/stdc++.h> #define endl '\n' #define space ' ' #define st first #define nd second #define pb push_back #define mp make_pair #define ii pair <int,int> #define iii pair <int,pair<int,int> > #define vi vector <int> #define vii vector < pair<int,int> > #define forr(i,A,B) for(int i=A;i<B;++i) #define input(file) freopen(file,"r",stdin) #define output(file) freopen(file,"w",stdout) #define time hdsadas #define edge xasdafsaf #define y1 dsafgsdfs #define MAXX 10 #define mod 1000000007 using namespace std; typedef pair<pair<int,int>,pair<int,int> > edge; inline void read(int &x){ scanf(" %d",&x); } const int maxn=3*100005; int n,m,k,qa[maxn],ql[maxn],qr[maxn],lo[maxn],hi[maxn],x,need[maxn]; vector <int> owner[maxn],tocheck[maxn]; long long sum,fw[maxn]; void upd(int x,int val){ if(x==0) return; for(;x<maxn;x+=(x&-x)){ fw[x]+=val; } } int que(int x){ int ret=0; for(;x>0;x-=(x&-x)) ret+=fw[x]; return ret; } void shower(int x){ if(ql[x]<=qr[x]){ upd(ql[x],qa[x]); upd(qr[x]+1,-qa[x]); } else{ upd(1,qa[x]); upd(qr[x]+1,-qa[x]); upd(ql[x],qa[x]); } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin>>n>>m; forr(i,0,m){ int x; cin>>x; owner[x].pb(i+1); } forr(i,0,n){ cin>>need[i+1]; } cin>>k; forr(i,1,k+1){ cin>>ql[i]>>qr[i]>>qa[i]; } forr(i,1,n+1){ lo[i]=1; hi[i]=k+1; } bool notdone=true; while(notdone){ notdone=false; memset(fw,0,sizeof fw); forr(i,1,n+1){ if(lo[i]!=hi[i]) tocheck[(lo[i]+hi[i])/2].pb(i); } forr(i,1,k+1){ shower(i); while(!tocheck[i].empty()){ notdone=true; sum=0; int id=tocheck[i].back(); tocheck[i].pop_back(); forr(j,0,owner[id].size()){ if(sum>=need[id]) break; sum+=que(owner[id][j]); } if(sum>=need[id]){ hi[id]=i; } else{ lo[id]=i+1; } } } } forr(i,1,n+1){ if(lo[i]==k+1) cout<<"NIE\n"; else cout<<lo[i]<<endl; } return 0; }

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
                                  ^
met.cpp:92:5: note: in expansion of macro 'forr'
     forr(j,0,owner[id].size()){
     ^
#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...