#ifdef LIS05ST
#define _GLIBCXX_DEBUG
#define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"plants.h"
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef long double ld;
const int NMAX=2e6;
int pref[NMAX+5];
int n,k;
int get(int l,int r){
return pref[r]-pref[l-1];
}
bool one(int l,int r){
return get(l,r)==r-l+1;
}
bool zero(int l,int r){
return get(l,r)==0;
}
vector<int>h;
int id(int x){
return (x%n+n)%n;
}
struct Node{
int min;
int pos;
ll padd;
};
Node tree[4*NMAX+5];
Node merge(Node a,Node b){
Node res;
res.min=min(a.min,b.min);
res.pos=-1;
if(a.min==res.min){
res.pos=max(res.pos,a.pos);
}
if(b.min==res.min){
res.pos=max(res.pos,b.pos);
}
res.padd=0;
return res;
}
vector<int>vec;
void build(int v,int l,int r){
if(l==r){
tree[v].min=vec[l];
tree[v].pos=l;
tree[v].padd=0;
return;
}
int m=(l+r)/2;
build(2*v,l,m);
build(2*v+1,m+1,r);
tree[v]=merge(tree[2*v],tree[2*v+1]);
}
void pushAdd(int v,int val){
tree[v].min+=val;
tree[v].padd+=val;
}
void push(int v,int l,int r){
pushAdd(2*v,tree[v].padd);
pushAdd(2*v+1,tree[v].padd);
tree[v].padd=0;
}
pair<int,int> get(int v,int l,int r,int l0,int r0,bool p=1){
//if(p)cout<<l<<":"<<r<<" "<<l0<<":"<<r0<<"\n";
//if(p)cout<<tree[2*v].min<<" "<<tree[2*v].pos<<"\n";
push(v,l,r);
if(r0<l||r<l0||tree[v].min!=0)return {1e9,1e9};
if(l0<=l&&r<=r0&&l==r)return {tree[v].min,tree[v].pos};
int m=(l+r)/2;
if(tree[2*v].min==0&&tree[2*v].pos>=l0)return get(2*v,l,m,l0,r0,p);
return get(2*v+1,m+1,r,l0,r0,p);
}
void add(int v,int l,int r,int l0,int r0,int val){
push(v,l,r);
if(r0<l||r<l0)return;
if(l0<=l&&r<=r0){
pushAdd(v,val);
return;
}
int m=(l+r)/2;
add(2*v,l,m,l0,r0,val);
add(2*v+1,m+1,r,l0,r0,val);
tree[v]=merge(tree[2*v],tree[2*v+1]);
}
void add(int l,int r,int val){
l-=3*n;r-=3*n;
for(auto e:vector<int>{0,1,2,3,4,5,6,7,8}){
if(0<=r&&r<=3*n-1){
int L=min(3*n-1,max(l,0));
int R=min(3*n-1,max(r,0));
add(1,0,3*n-1,L,R,val);
}
else if(0<=l&&l<=3*n-1){
int L=min(3*n-1,max(l,0));
int R=min(3*n-1,max(r,0));
add(1,0,3*n-1,L,R,val);
}
l+=n;r+=n;
}
}
int step;
void extract(int pos){
while(true){
auto [a,b]=get(1,0,3*n-1,pos-k+1,pos-1);
if(a==0)extract(b);
else break;
}
h[pos%n]=step--;
add(pos-k+1,pos-1,-1);
add(pos,pos,1e9);
}
int dist(int u,int v){
return min(abs(u-v),abs(u+n-v),abs(v+n-u));
}
int d1[300+5][300+5];
int d2[300+5][300+5];
void init(int K, std::vector<int> rr){
n=rr.size();h.resize(n);
k=K;
for(int i=0;i<n;i++)pref[i+1]=pref[i]+rr[i];
for(int e=0;e<3;e++)for(int i=0;i<n;i++){
vec.push_back(rr[i]);
}
//for(auto e:vec)cout<<e<<" ";cout<<"\n";
build(1,0,3*n-1);
int L=0+n+n;int R=n-1+n+n;
step=n;
while(step>=1){
auto[val,pos]=get(1,0,3*n-1,L,R);
extract(pos);
}
if(n<=300){
for(int i=0;i<=n;i++)for(int ii=0;ii<=n;ii++)d1[i][ii]=d2[i][ii]=1e9;
for(int i=0;i<n;i++){
for(int ii=0;ii<n;ii++){
if(i==ii)continue;
if(dist(i,ii)<k){
if(h[i]>h[ii])d1[i][ii]=1;
if(h[i]<h[ii])d2[i][ii]=1;
}
}
}
for(int i=0;i<n;i++)
for(int ii=0;ii<n;ii++)
for(int iii=0;iii<n;iii++)
{
if(i==ii||i==iii||ii==iii)continue;
d1[i][ii]=min(d1[i][ii],d1[i][iii]+d1[iii][ii]);
d2[i][ii]=min(d2[i][ii],d2[i][iii]+d2[iii][ii]);
}
}
//for(auto e:h)cout<<e<<" ";cout<<endl;
};
int compare_plants(int x, int y){
if(k==2){
x++,y++;
if(zero(x,y-1))return 1;
if(one(1,x-1)&&one(y,n))return 1;
if(one(x,y-1))return -1;
if(zero(1,x-1)&&zero(y,n))return -1;
return 0;
}
if(n<=300){
if(d1[x][y]<1e6)return 1;
if(d2[x][y]<1e6)return -1;
return 0;
}
if(h[x]>h[y])return 1;
if(h[x]<h[y])return -1;
return 0;
}
#define MULTITESTS false
void solve(int testCase){
}
// x y
void precalc(){
}
/*
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
precalc();
int t=1;
if(MULTITESTS)cin>>t;
for(int i=1;i<=t;i++){
auto t1=clock();
solve(i);
auto t2=clock();
float delta=t2-t1;
delta/=CLOCKS_PER_SEC;
#ifdef LIS05ST
cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
#endif
}
}*/
Compilation message
plants.cpp: In function 'void add(int, int, int)':
plants.cpp:104:14: warning: unused variable 'e' [-Wunused-variable]
104 | for(auto e:vector<int>{0,1,2,3,4,5,6,7,8}){
| ^
In file included from /usr/include/c++/10/vector:60,
from plants.h:1,
from plants.cpp:7:
/usr/include/c++/10/bits/stl_algobase.h: In instantiation of 'constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare) [with _Tp = int; _Compare = int]':
plants.cpp:132:46: required from here
/usr/include/c++/10/bits/stl_algobase.h:281:17: error: '__comp' cannot be used as a function
281 | if (__comp(__b, __a))
| ~~~~~~^~~~~~~~~~
