Submission #302607

#TimeUsernameProblemLanguageResultExecution timeMemory
302607Dremix10Comparing Plants (IOI20_plants)C++17
14 / 100
4102 ms19448 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pl; #define F first #define S second #define endl '\n' #define all(x) (x).begin(),(x).end(); #define p(x) cerr<<#x<<" = "<<x<<endl; #define p2(x,y) cerr<<#x<<","<<#y<<" = "<<"("<<x<<"-"<<y<<")"<<endl; #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl; vector<int> arr,bigger; vector<int> seg; vector<int> laz; vector<int> pou; void join(int par, int x, int y){ if(seg[x]<seg[y]){ seg[par] = seg[x]; pou[par] = pou[x]; } else{ seg[par] = seg[y]; pou[par] = pou[y]; } } void push(int par, int x, int y){ seg[x] += laz[par]; laz[x] += laz[par]; seg[y] += laz[par]; laz[y] += laz[par]; laz[par] = 0; } void build(int s, int e, int idx){ if(s==e){ seg[idx] = 1e9; pou[idx] = s; return; } int mid = (s+e)/2; build(s,mid,idx*2); build(mid+1,e,idx*2+1); join(idx,idx*2,idx*2+1); } void update(int s, int e, int idx, int qs, int qe, int x){ if(qs<=s && e<=qe){ seg[idx] += x; laz[idx] += x; return; } if(s>qe || e<qs)return; int mid = (s+e)/2; push(idx,idx*2,idx*2+1); update(s,mid,idx*2,qs,qe,x); update(mid+1,e,idx*2+1,qs,qe,x); join(idx,idx*2,idx*2+1); //p2(s,e) //p2(seg[idx],pou[idx]) } void init(int k, vector<int> r) { int n = r.size(); arr.assign(n,0); bigger.assign(n,0); seg.assign((n+5)*4,0); laz.assign((n+5)*4,0); pou.assign((n+5)*4,0); int i,j; build(0,n-1,1); for(i=0;i<n;i++){ if(r[i]==0){ p(i) p2(i+k-1,n) if(i+1<n){ update(0,n-1,1,i+1,min(n-1,i+k-1),1); } if(i+k-1>=n){ p((i+k-1)%n) update(0,n-1,1,0,(i+k-1)%n,1); } update(0,n-1,1,i,i,-1e9); } } int curr = n; for(int t=0;t<n;t++){ int x = pou[1]; //p2(pou[1],seg[1]) arr[x] = curr--; update(0,n-1,1,x,x,1e9); //pv(arr) //for(auto xx : s) // cout<<xx.pos<<" "; //cout<<endl; //pv(bigger) //pv(r) //cout<<endl; if(x+1<n){ update(0,n-1,1,x+1,min(n-1,x+k-1),-1); } if(x+k-1>=n){ update(0,n-1,1,0,(x+k-1)%n,-1); } for(j=1;j<k;j++){ //cout<<j<<" "<<k<<endl; int idx = x-j; if(idx<0)idx+=n; if(r[idx]>0){ r[idx]--; if(r[idx]==0){ if(idx+1<n){ update(0,n-1,1,idx+1,min(n-1,idx+k-1),1); } if(idx+k-1>=n){ update(0,n-1,1,0,(idx+k-1)%n,1); } update(0,n-1,1,idx,idx,-1e9); } } } //pv(bigger) //pv(zer) //pv(r) } pv(arr) } int compare_plants(int x, int y) { if(arr[x]>arr[y])return 1; return -1; }
#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...