#include "plants.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x) cerr<< #x <<" = "<< x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int h[MAXN],n,k,arr[MAXN];
vector<int>tmp;
struct tree{
PII s[MAXN<<2];int lazy[MAXN<<2];
void build(int nd=1,int x=0,int y=n-1){
lazy[nd]=0;
if(x==y){
s[nd]=mp(arr[x],x);
return;
}
int mid=(x+y)>>1;
build(nd<<1,x,mid);
build(nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void shift(int nd){
int &ret=lazy[nd];if(!ret)return;
lazy[nd<<1]+=ret;s[nd<<1].ff+=ret;
lazy[nd<<1|1]+=ret;s[nd<<1|1].ff+=ret;
ret=0;
}
void inc(int l,int r,int val,int nd=1,int x=0,int y=n-1){
if(l>y or x>r)
return;
if(l<=x and y<=r){
s[nd].ff+=val;
lazy[nd]+=val;
return;
}
shift(nd);
int mid=(x+y)>>1;
inc(l,r,val,nd<<1,x,mid);
inc(l,r,val,nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void print(int nd=1,int x=0,int y=n-1){
if(x==y){
printf("%d ",s[nd].ff);
return;
}shift(nd);
int mid=(x+y)>>1;
print(nd<<1,x,mid);
print(nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
void tap(int l,int r,int nd=1,int x=0,int y=n-1){
if(l>y or x>r or s[nd].ff>0)return;
if(x==y){
tmp.pb(x);
return;
}shift(nd);
int mid=(x+y)>>1;
tap(l,r,nd<<1,x,mid);
tap(l,r,nd<<1|1,mid+1,y);
s[nd]=min(s[nd<<1],s[nd<<1|1]);
}
}ds[2];
void upd(int x,int y,int val,int bro=1){
if(x<=y){
ds[0].inc(x,y,val);
if(bro)ds[1].inc(x,y,val);
}
else{
ds[0].inc(x,n-1,val),ds[0].inc(0,y,val);
if(bro)ds[1].inc(x,n-1,val),ds[1].inc(0,y,val);
}
}
int get(){
int a=ds[0].s[1].ff;
int b=ds[0].s[1].ss;
assert(a==0);return b;
}
int vis[MAXN];
void zero(int i){
if(vis[i])return;vis[i]=1;
//printf("zero %d\n",i);
upd(i+1,(i+k-1)%n,1,0);
}
void flex(int x,int y){
if(x<=y)ds[1].tap(x,y);
else ds[1].tap(x,n-1),ds[1].tap(0,y);
}
int d(int x,int y){
if(x>y)swap(x,y);
return min(y-x,n-x+y);
}
set<PII>st;
int l[MAXN],r[MAXN];
void init(int K, vector<int> r) {
n=int(r.size());k=K;
for(int i=0;i<n;i++)arr[i]=r[i];
ds[0].build();ds[1].build();
for(int i=0;i<n;i++)
if(!arr[i])
zero(i);
for(int i=n-1;i>=0;i--){
int res=get();assert(res>=0 and res<n);h[res]=i;
//debug(res);
int pre=(res-K+1+n)%n;
int nex=(res+K-1)%n;
upd(res,res,INF);
upd(pre,res,-1);upd(res,nex,-1,0);
flex(pre,res);flex(res,nex);
//ds[0].print();puts("");
tr(it,tmp)zero(*it);tmp.clear();
//ds[1].print();
//puts("");puts("");
}
int p=n-k+1;
for(int i=p;i<n;i++)
st.insert(mp(h[i],i));
for(int i=0;i<n;i++){
__typeof((st).begin())it=st.lower_bound(mp(h[i],-1));
if(it!=st.begin()){
it--;l[i]=it->ss;
}
else
l[i]=-1;
st.erase(mp(arr[p],p));p=(p+1)%n;
st.insert(mp(arr[i],i));
}st.clear();
p=k-2;
for(int i=0;i<=p;i++)st.insert(mp(arr[i],i));
for(int i=n-1;i>=0;i--){
__typeof((st).begin())it=st.lower_bound(mp(h[i],-1));
if(it!=st.begin()){
it--;r[i]=it->ss;
}
else
r[i]=-1;
st.erase(mp(arr[p],p));p=(p-1+n)%n;
st.insert(mp(arr[i],i));
}
}
int compare_plants(int x, int y) {
if(d(x,y)<k){
if(h[x]>h[y])return 1;
else return -1;
}
else{int a;
a=x;while(~l[a] and a<=x)a=l[a];
while(~l[a] and l[a]>y)a=l[a];
if(d(a,y)<k and h[a]>h[y])return 1;
a=x;while(~r[a] and r[a]<y)a=r[a];
if(d(a,y)<k and h[a]>h[y])return 1;
a=y;while(~l[a] and l[a]>x)a=l[a];
if(d(a,x)<k and h[a]>h[x])return -1;
a=y;while(~r[a] and y<=a)a=r[a];
while(~r[a] and r[a]<x)a=r[a];
if(d(a,x)<k and h[a]>h[x])return -1;
}
return 0;
}
Compilation message
plants.cpp: In function 'void zero(int)':
plants.cpp:95:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
95 | if(vis[i])return;vis[i]=1;
| ^~
plants.cpp:95:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
95 | if(vis[i])return;vis[i]=1;
| ^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:10:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
10 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
| ^~~
plants.cpp:125:3: note: in expansion of macro 'tr'
125 | tr(it,tmp)zero(*it);tmp.clear();
| ^~
plants.cpp:125:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
125 | tr(it,tmp)zero(*it);tmp.clear();
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4074 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4046 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4046 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
12908 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12908 KB |
Output is correct |
| 3 |
Execution timed out |
4022 ms |
17024 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4083 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4089 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
12908 KB |
Output is correct |
| 2 |
Execution timed out |
4074 ms |
12908 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
