Submission #1202694

#TimeUsernameProblemLanguageResultExecution timeMemory
1202694ASGA_RedSeaFinding Routers (IOI20_routers)C++20
98.88 / 100
2 ms1608 KiB
/** * بسم الله الرحمن الرحيم * ﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿ */ /// author : "Ahmed Samed Gomaa" #pragma GCC optimize("Ofast") #include<bits/stdc++.h> int use_detector(int x); using namespace std; using ll=long long; struct sgt{ vector<int>s; int sz,lg; void init(int n){ lg=__lg(n)+1; sz=1<<lg; s.assign(sz*2,0); } void edit(int i,int v){ i+=sz; s[i]=v; while(i>1){ i>>=1; s[i]=max(s[i*2],s[i*2+1]); } } int get(int v){ if(s[1]<=v)return sz; int i=1; while(i<sz){ if(s[i*2]>v)i*=2; else i=i*2+1; } return i-sz-1; } }; sgt s; vector<int>v; int q; int ask(int x){ if(v[x]==-1){ assert(q>0); q--; v[x]=use_detector(x); s.edit(x,v[x]); } return v[x]; } vector<int>find_routers(int _l,int n,int Q){ q=Q; v.assign(_l+1,-1); s.init(_l+1); //if(Q==2e4)for(int i=320;i<=_l;i+=320)ask(i); vector<int>ans; int cur=0; for(int i=0;i<n;i++){ if(i==0){ ans.push_back(0); } else{ int L=cur-1; ans.push_back(L-ans.back()+L); } if(i+1<n){ int l=cur,r=min(_l,s.get(i)),m; while(l<=r){ m=(l+r)/2; if(ask(m)>i)r=m-1; else l=m+1; } cur=l; } } return ans; } //signed main(){ // ios_base::sync_with_stdio(0);cin.tie(0); // // // ; // // // 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...