#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int n, pos[200100],CA;
vector<int> R;
set<int> CD;
set<pair<int,int>> gaps;
int bjl[200100][20],bjr[200100][20], gooverL[200100], gooverR[200100];
struct segtree{
pair<int,int> T[1<<19];
int lz[1<<20];
inline void pd(int i){
if(lz[i]){
T[i].first+=lz[i];
lz[i*2]+=lz[i];
lz[i*2+1]+=lz[i];
lz[i]=0;
}
}
void init(int i,int l,int r){
if(l==r)return void(T[i]={R[l],l});
init(i*2,l,l+r>>1);
init(i*2+1,l+r+2>>1,r);
T[i]=min(T[i*2],T[i*2+1]);
}
void upd(int i,int l,int r,int ll,int rr){
pd(i);if(ll<=l&&r<=rr)
return lz[i]=-1,pd(i);
if(l>rr||ll>r)return;
upd(i*2,l,l+r>>1,ll,rr);
upd(i*2+1,l+r+2>>1,r,ll,rr);
T[i]=min(T[i*2],T[i*2+1]);
}
void upd2(int i,int l,int r,int ll,int rr){
pd(i);if(ll<=l&&r<=rr)
return lz[i]=1e9,pd(i);
if(l>rr||ll>r)return;
upd2(i*2,l,l+r>>1,ll,rr);
upd2(i*2+1,l+r+2>>1,r,ll,rr);
T[i]=min(T[i*2],T[i*2+1]);
}
}ST;
inline int AGL(int k){
return (k+n)%n;
}
inline void add(int i){
if(!CD.size()){
gaps.insert({n,i});
CD.insert(i);
return;
}
if(CD.size()==1){
CD.insert(i);
gaps.clear();
int a=*CD.begin();
int b=*--CD.end();
gaps.insert({b-a,b});
gaps.insert({n+a-b,a});
return;
}
auto it1=CD.upper_bound(i);
auto it2=it1;
if(it2==CD.begin())
it2=--CD.end();
else --it2;
if(it1==CD.end())
it1=CD.begin();
gaps.insert({AGL(i-*it2),i});
gaps.insert({AGL(*it1-i),*it1});
gaps.erase({AGL(*it1-*it2),*it1});
CD.insert(i);
}
inline void del(int i){
if(CD.size()==1)
return CD.clear(),gaps.clear();
else if(CD.size()==2){
CD.erase(i);
gaps.clear();
gaps.insert({n,*CD.begin()});
return;
}
auto it1=CD.upper_bound(i);
auto it2=CD.find(i);
if(it2==CD.begin())
it2=--CD.end();
else --it2;
if(it1==CD.end())
it1=CD.begin();
gaps.erase({AGL(i-*it2),i});
gaps.erase({AGL(*it1-i),*it1});
gaps.insert({AGL(*it1-*it2),*it1});
CD.erase(i);
}
inline int possiblemin(){
auto[a,b]=ST.T[1];
if(!a) {
ST.upd2(1,0,n-1,b,b);
add(b);
return 1;
}
return 0;
}
void init(int k, std::vector<int> r) {
R=r;
k--;
n=r.size();
ST.init(1,0,n-1);
while(possiblemin());
while(CD.size()){
int bst=(--gaps.end())->second;
pos[bst]=++CA;
if(bst<k)ST.upd(1,0,n-1,0,bst),
ST.upd(1,0,n-1,bst-k+n,n-1);
else ST.upd(1,0,n-1,bst-k,bst);
while(possiblemin());
del(bst);
}
set<pair<int,int>> st;
st.insert({1e9,n});
for(int i=n-k;i<n;i++)
st.insert({pos[i],i});
for(int i=0;i<n;i++)bjl[i][0]=st.upper_bound({pos[i],0})->second,
st.erase({pos[(i+n-k)%n],(i+n-k)%n}),st.insert({pos[i],i});
st.clear();
for(int i=0;i<k;i++)
st.insert({pos[i],i});
st.insert({1e9,n});
bjl[n][0]=bjr[n][0]=n;
for(int i=n;i--;)bjr[i][0]=st.upper_bound({pos[i],0})->second,
st.erase({pos[(i+k)%n],(i+k)%n}),st.insert({pos[i],i});
for(int i=0;i<n;i++)
if(bjl[i][0]>i&&bjl[i][0]-n)
gooverL[i]=bjl[i][0],bjl[i][0]=i;
for(int i=0;i<n;i++)
if(bjr[i][0]<i&&bjr[i][0]-n)
gooverR[i]=bjr[i][0],bjr[i][0]=i;
for(int j=1;j<20;j++) for(int i=0;i<=n;i++)
bjl[i][j]=bjl[bjl[i][j-1]][j-1],
bjr[i][j]=bjr[bjr[i][j-1]][j-1];
pos[n]=1e9;
}
int biggerl(int x,int y){
int prevx=x;
if(x<y)x=gooverL[bjl[x][19]];
if(x<=y) return pos[bjl[prevx][19]]<=pos[y];
for(int i=20;i--;)
if(bjl[x][i]>=y&&bjl[x][i]-n)
x=bjl[x][i];
if(bjl[x][0]==n)
return 0;
return pos[x]<=pos[y];
}
int biggerr(int x,int y){
int prevx=x;
if(x>y)x=gooverR[bjr[x][19]];
if(x>=y) return pos[bjr[prevx][19]]<=pos[y];
for(int i=20;i--;)
if(bjr[x][i]<=y&&bjr[x][i]-n)
x=bjr[x][i];
if(bjr[x][0]==n)
return 0;
return pos[x]<=pos[y];
}
inline int bigger(int x,int y){
return biggerl(x,y)||biggerr(x,y);
}
int compare_plants(int x, int y) {
if(pos[x]<pos[y])
return bigger(x,y)?1:0;
return bigger(y,x)?-1:0;
}
Compilation message
plants.cpp: In member function 'void segtree::init(int, int, int)':
plants.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | init(i*2,l,l+r>>1);
| ~^~
plants.cpp:23:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | init(i*2+1,l+r+2>>1,r);
| ~~~^~
plants.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
plants.cpp:30:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | upd(i*2,l,l+r>>1,ll,rr);
| ~^~
plants.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | upd(i*2+1,l+r+2>>1,r,ll,rr);
| ~~~^~
plants.cpp: In member function 'void segtree::upd2(int, int, int, int, int)':
plants.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | upd2(i*2,l,l+r>>1,ll,rr);
| ~^~
plants.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | upd2(i*2+1,l+r+2>>1,r,ll,rr);
| ~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10844 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10848 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10840 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10844 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
