| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 613872 | Koosha_mv | Comparing Plants (IOI20_plants) | C++14 | 0 ms | 0 KiB |
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;
#define dbgv(v) cout<<#v<<" = "; f(i,0,int(v.size())) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=2e5+99,lg=20;
int n,k,p[N],a[N],pos[N],vis[N][N],seg[N<<2],lz[N<<2];
vector<int> vec;
set<int> s,ok;
pair<int,int> A[lg][N],B[lg][N];
void check(int x){
int len;
if(x==*s.begin()){
len=x-(*s.rbegin())+n;
}
else{
len=x-(*prev(s.lower_bound(x)));
}
if(len>=k){
ok.insert(x);
}
else{
if(ok.find(x)!=ok.end()){
ok.erase(x);
}
}
}
void adds(int x){
s.insert(x);
check(x);
if(x==*s.rbegin()){
check(*s.begin());
}
else{
check(*s.upper_bound(x));
}
}
void dels(int x){
s.erase(x);
if(*s.rbegin()<x){
check(*s.begin());
}
else{
check(*s.upper_bound(x));
}
}
void upd(int id){
seg[id]=min(seg[id<<1],seg[id<<1|1]);
}
void shift(int id){
lz[id<<1]+=lz[id];
lz[id<<1|1]+=lz[id];
seg[id<<1]+=lz[id];
seg[id<<1|1]+=lz[id];
lz[id]=0;
}
void build(int id=1,int l=0,int r=n){
if(l+1==r){
seg[id]=p[l];
return ;
}
int mid=(l+r)>>1;
build(id<<1,l,mid);
build(id<<1|1,mid,r);
upd(id);
}
void prt(int L,int R,int id=1,int l=0,int r=n){
//cout<<L<<" "<<R<<" "<<id<<" "<<l<<" "<<r<<endl;
//eror(seg[id]);
if(seg[id]>1 || r<=L || R<=l) return ;
if(l+1==r){
vec.pb(l);
adds(l);
return ;
}
int mid=(l+r)>>1;
shift(id);
prt(L,R,id<<1,l,mid);
prt(L,R,id<<1|1,mid,r);
upd(id);
}
void add(int L,int R,int val,int id=1,int l=0,int r=n){
if(r<=L || R<=l) return ;
if(L<=l && r<=R){
lz[id]+=val;
seg[id]+=val;
return ;
}
int mid=(l+r)>>1;
shift(id);
add(L,R,val,id<<1,l,mid);
add(L,R,val,id<<1|1,mid,r);
upd(id);
}
void builda(){
build();
f(i,0,n){
if(p[i]==0){
s.insert(i);
}
}
f(i,0,n){
if(p[i]==0){
add(i,i+1,n+10);
check(i);
}
}
f_(T,n-1,0){
int x=(*ok.begin());
//eror(x);
ok.erase(x);
a[x]=T;
if(T==0) break ;
int l=(x-k+n+1)%n,r=x;
vec.clear();
if(r<l){
prt(0,r);
prt(l,n);
add(0,r,-1);
add(l,n,-1);
//dbgv(vec);
}
else{
prt(l,r);
add(l,r,-1);
}
dels(x);
for(auto g : vec) add(g,g+1,n+10);
}
/*int last=0;
f_(T,n-1,0){
f(i,0,2*n){
if(p[i%n]==0){
if(i>=n && i-last>=k){
a[i-n]=T;
f(j,0,k){
p[(i-j)%n]--;
}
break ;
}
last=i;
}
}
}*/
f(i,0,n) pos[a[i]]=i;
//dbga(a,0,n);
}
void AB(){
set<int> s;
f(i,0,k-1) s.insert(a[i]);
f_(i,n-1,0){
int ida=-1,idb=-1;
if(*s.begin()<a[i]){
ida=pos[*prev(s.lower_bound(a[i]))];
}
if(*s.rbegin()>a[i]){
idb=pos[*s.lower_bound(a[i])];
}
s.insert(a[i]);
s.erase(a[(i+k-1)%n]);
if(ida==-1){
A[0][i]={i,0};
}
else{
A[0][i]={ida,(ida-i+n)%n};
}
if(idb==-1){
B[0][i]={i,0};
}
else{
B[0][i]={idb,(idb-i+n)%n};
}
}
f(l,1,lg){
f(i,0,n){
A[l][i]={A[l-1][A[l-1][i].F].F,A[l-1][i].S+A[l-1][A[l-1][i].F].S};
B[l][i]={B[l-1][B[l-1][i].F].F,B[l-1][i].S+B[l-1][B[l-1][i].F].S};
}
}
}
bool checkA(int u,int v){
int len=(v-u+n)%n;
f_(l,lg-1,0){
if(A[l][u].S<=len){
len-=A[l][u].S;
u=A[l][u].F;
}
}
if((v-u+n)%n<k && a[u]>=a[v]) return 1;
return 0;
}
bool checkB(int u,int v){
int len=(v-u+n)%n;
f_(l,lg-1,0){
if(B[l][u].S<=len){
len-=B[l][u].S;
u=B[l][u].F;
}
}
if((v-u+n)%n<k && a[u]<=a[v]) return 1;
return 0;
}
void init(int _k,vector<int> _p) {
n=_p.size(),k=_k;
f(i,0,n) p[i]=_p[i];
builda();
AB();
}
int compare_plants(int x, int y) {
if(checkA(x,y) || checkB(y,x)) return 1;
if(checkB(x,y) || checkA(y,x)) return -1;
return 0;
}