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 <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int pot=1<<18,N=200007,L=18;
int n;
struct T
{
pair<int,int> seg[2*pot+7];
int lzy[2*pot+7];
T()
{
memset(seg,0,sizeof seg);
memset(lzy,0,sizeof lzy);
}
void push(int v)
{
lzy[2*v]+=lzy[v];
lzy[2*v+1]+=lzy[v];
seg[2*v].st+=lzy[v];
seg[2*v+1].st+=lzy[v];
lzy[v]=0;
}
void add(int v,int a,int b,int l,int r,int x)
{
if(a<=l&&b>=r)
{
lzy[v]+=x;
seg[v].st+=x;
return ;
}
if(r<a||l>b) return ;
push(v);
add(2*v,a,b,l,(l+r)/2,x);
add(2*v+1,a,b,(l+r)/2+1,r,x);
seg[v]=min(seg[2*v],seg[2*v+1]);
}
};
vector<int>p;
int skokR[2*N][L];
int skokL[2*N][L];
void init(int k,vector<int>r)
{
n=sz(r);
p.resize(2*n+2);
T R,ile;
for(int i=0;i<n;i++) R.seg[i+pot]={r[i],i+1};
for(int i=n+1;i<=pot;i++) R.seg[i+pot-1]={inf,i};
for(int i=1;i<=pot;i++) ile.seg[i+pot-1]={inf,i};
for(int i=pot-1;i>0;i--)
{
R.seg[i]=min(R.seg[2*i],R.seg[2*i+1]);
ile.seg[i]=min(ile.seg[2*i],ile.seg[2*i+1]);
}
int it=0;
while(it<n)
{
while(R.seg[1].st==0)
{
int i=R.seg[1].nd;
R.add(1,i,i,1,pot,inf);
ile.add(1,i,i,1,pot,-inf);
if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,1);
else
{
ile.add(1,i+1,n,1,pot,1);
ile.add(1,1,i+k-1-n,1,pot,1);
}
}
int i=ile.seg[1].nd;
ile.add(1,i,i,1,pot,inf);
p[i]=n-it++;
if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,-1);
else
{
ile.add(1,i+1,n,1,pot,-1);
ile.add(1,1,i+k-1-n,1,pot,-1);
}
if(i-k+1>0) R.add(1,i-k+1,i-1,1,pot,-1);
else
{
R.add(1,i-k+1+n,n,1,pot,-1);
R.add(1,1,i-1,1,pot,-1);
}
}
for(int i=n+1;i<=2*n;i++) p[i]=p[i-n];
p[2*n+1]=inf;
p[0]=inf;
set<pair<int,int>>S;
S.insert({inf,0});
for(int i=1;i<=2*n;i++)
{
if(i-k>0) S.erase({p[i-k],i-k});
pair<int,int>x=*S.upper_bound({p[i],i});
if(x.st==inf) skokR[i][0]=i;
else skokR[i][0]=x.nd;
S.insert({p[i],i});
}
S.clear();
S.insert({inf,0});
for(int i=2*n;i>0;i--)
{
if(i+k<=2*n) S.erase({p[i+k],i+k});
pair<int,int>x=*S.upper_bound({p[i],i});
if(x.st==inf) skokL[i][0]=i;
else skokL[i][0]=x.nd;
S.insert({p[i],i});
}
for(int j=1;j<L;j++)
{
for(int i=1;i<=2*n;i++)
{
skokL[i][j]=skokL[skokL[i][j-1]][j-1];
skokR[i][j]=skokR[skokR[i][j-1]][j-1];
}
}
/* for(int i=1;i<=2*n;i++) cout<<p[i]<<" ";
cout<<endl;
for(int i=1;i<=2*n;i++) cout<<skokL[i][0]<<" ";
cout<<endl;
for(int i=1;i<=2*n;i++) cout<<skokR[i][0]<<" ";
cout<<endl;*/
}
int compare_plants(int x,int y)
{
x++,y++;
bool is=0;
int f=1;
if(p[x]<p[y])
{
swap(x,y);
f=-1;
}
int Y=y;
for(int j=L-1;j>=0;j--) if(p[skokL[Y][j]]<=p[x]) Y=skokL[Y][j];
if(x>y&&Y>=x) is=1;
if(x<y&&Y>=x+n) is=1;
Y=y+n;
for(int j=L-1;j>=0;j--) if(p[skokR[Y][j]]<=p[x]) Y=skokR[Y][j];
if(x<y&&Y<=x+n) is=1;
if(x>y&&Y<=x) is=1;
if(is) return f;
else return 0;
}
/*
int main()
{
/*int n,k;
cin>>n>>k;
vector<int>q(n);
for(int i=0;i<n;i++) q[i]=i+1;
random_shuffle(all(q));
vector<int>r(n,0);
for(int i=0;i<n;i++)
{
for(int j=i;j<i+k;j++) if(q[i]<q[j%n]) r[i]++;
}
for(int i=0;i<n;i++) cout<<q[i]<<" ";
cout<<endl;
for(int i=0;i<n;i++) cout<<r[i]<<" ";
cout<<endl;
init(k,r);
int Q=50;
while(Q--)
{
cout<<compare_plants(rand()%n,rand()%n)<<endl;
}
return 0;
}
*/
Compilation message (stderr)
plants.cpp:166:5: warning: "/*" within comment [-Wcomment]
166 | /*int n,k;
|
plants.cpp: In constructor 'T::T()':
plants.cpp:26:32: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
26 | memset(seg,0,sizeof seg);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from plants.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
211 | struct pair
| ^~~~
# | 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... |