This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
int n;
pair <int,int> seg[800040];
int laz[800040],arr[200010];
void build(int id,int tl,int tr){
if (tl==tr){
seg[id]={arr[tl],tl};
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
seg[id]=min(seg[2*id],seg[2*id+1]);
}
void pushdown(int id,int tl,int tr){
seg[2*id].first+=laz[id]; laz[2*id]+=laz[id];
seg[2*id+1].first+=laz[id]; laz[2*id+1]+=laz[id];
laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r,int val){
if (l>r) return;
if (l<=tl&&tr<=r){
seg[id].first+=val;
laz[id]+=val;
return;
}
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
update(2*id,tl,tm,l,min(r,tm),val);
update(2*id+1,tm+1,tr,max(l,tm+1),r,val);
seg[id]=min(seg[2*id],seg[2*id+1]);
}
pair <int,int> query(int id,int tl,int tr,int l,int r){
if (l>r) return {1e9,1e9};
if (l<=tl&&tr<=r) return seg[id];
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
pair <int,int> lx=query(2*id,tl,tm,l,min(r,tm));
pair <int,int> rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
return min(lx,rx);
}
vector <int> p;
set <int> s;
set <pair <int,int>,greater <pair <int,int> > > diff;
void add_s(int u){
if (s.empty()){
s.insert(u);
return;
}
if (s.size()==1){
int prv=*s.begin();
s.insert(u);
if (prv>u) swap(prv,u);
diff.insert({u-prv,u});
diff.insert({prv-u+n,prv});
return;
}
auto it=s.lower_bound(u);
if (it==s.end()) it=s.begin();
int nxt=(*it);
if (it==s.begin()) it=s.end();
it--;
int prv=(*it);
diff.erase({(nxt>prv?nxt-prv:nxt-prv+n),nxt});
diff.insert({(u>prv?u-prv:u-prv+n),u});
diff.insert({(nxt>u?nxt-u:nxt-u+n),nxt});
s.insert(u);
}
void del_s(int u){
if (s.size()<=2){
s.erase(u);
diff.clear();
return;
}
auto it=s.lower_bound(u);
auto it2=it;
it2++;
if (it2==s.end()) it2=s.begin();
int nxt=(*it2);
it2=it;
if (it2==s.begin()) it2=(--s.end());
else it2--;
int prv=(*it2);
diff.erase({(u>prv?u-prv:u-prv+n),u});
diff.erase({(nxt>u?nxt-u:nxt-u+n),nxt});
diff.insert({(nxt>prv?nxt-prv:nxt-prv+n),nxt});
s.erase(u);
}
int get_s(){
if (s.size()==1) return *s.begin();
pair <int,int> tp=*diff.begin();
return tp.second;
}
void init(int k,vector <int> r){
n=r.size();
r.insert(r.begin(),0);
p.resize(n+1);
for (int i=1; i<=n; i++) arr[i]=r[i];
build(1,1,n);
for (int i=n; i; i--){
while (1){
pair <int,int> tp=query(1,1,n,1,n);
if (tp.first) break;
add_s(tp.second);
update(1,1,n,tp.second,tp.second,1e9);
}
int idx=get_s();
p[idx]=i;
if (idx>=k) update(1,1,n,idx-k+1,idx,-1);
else {
update(1,1,n,1,idx,-1);
update(1,1,n,n-(k-idx)+2,n,-1);
}
del_s(idx);
}
}
int compare_plants(int x,int y){
x++; y++;
if (p[x]>p[y]) return 1;
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |