#include<bits/stdc++.h>
#include "plants.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=4e5+10;
const int SS=1<<19;
const int INFi=1e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,lazy[SS*2+10],k,li,t2[N],g[N],jp[N][L];
pair<int,int> seg[SS*2+10];
void push(int v){
seg[v*2].fi+=lazy[v],seg[v*2+1].fi+=lazy[v];
lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
if(p>b or k<a) return;
if(p>=a and k<=b){
lazy[v]+=x,seg[v].fi+=x;
return;
}
int sr=(p+k)/2;
push(v);
upd(a,b,x,p,sr,v*2),upd(a,b,x,sr+1,k,v*2+1);
if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
else seg[v]=seg[v*2+1];
}
pair<int,int> qr(int a,int b,int p=0,int k=SS-1,int v=1){
if(p>b or k<a) return {INFi,-1};
if(p>=a and k<=b) return seg[v];
push(v);
int sr=(p+k)/2;
pair<int,int> q1=qr(a,b,p,sr,v*2),q2=qr(a,b,sr+1,k,v*2+1);
if(q1.fi<q2.fi) return q1;
return q2;
}
void build(int v){
if(v>=SS){
int id=v-SS;
if(id>=1 and id<=n) seg[v]={t[id],id};
else seg[v]={INFi,id};
}else{
build(v*2),build(v*2+1);
if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
else seg[v]=seg[v*2+1];
}
}
void zn(int a){
if(a>=k){
pair<int,int> xd=qr(a-k+1,a-1);
if(xd.fi==0) zn(xd.se);
t2[a]=--li;
}else{
pair<int,int> xd=qr(1,a-1);
if(xd.fi==0) zn(xd.se);
else{
xd=qr(n-(k-a)+1,n);
if(xd.fi==0) zn(xd.se);
}
t2[a]=--li;
}
if(a>=k) upd(a-k+1,a-1,-1);
else{
upd(1,a-1,-1);
upd(n-(k-a)+1,n,-1);
}
upd(a,a,INFi);
}
void init(int kk,vi r){
k=kk;
n=r.size();
for(int i=1;i<=n;i++) t[i]=r[i-1];
build(1);
li=n+1;
pair<int,int> curr=qr(1,n);
while(curr.fi==0){
zn(curr.se);
curr=qr(1,n);
}
for(int i=n+1;i<=n*2;i++) t2[i]=t2[i-n];
for(int i=1;i<=n*2;i++) g[t2[i]]=i;
n*=2;
for(int i=1;i<=n;i++) t[i]=INFi;
build(1);
n/=2;
for(int i=n;i>=1;i--){
upd(g[i],g[i],-INFi+g[i]);
upd(g[i]+n,g[i]+n,-INFi+g[i]);
pair<int,int> xd=qr(g[i]+1,g[i]+k-1);
if(xd.fi>=INFi) jp[g[i]][0]=g[i],jp[g[i]+n][0]=n+g[i];
else{
jp[g[i]][0]=xd.se;
if(xd.se<=n) jp[g[i]+n][0]=xd.se+n;
else jp[g[i]+n][0]=g[i]+n;
}
}
//for(int i=1;i<=n;i++) cout<<jp[i][0]<<" ";
//cout<<"\n";
for(int i2=1;i2<L;i2++){
for(int i=1;i<=n*2;i++) jp[i][i2]=jp[jp[i][i2-1]][i2-1];
}
}
int compare_plants(int x,int y){
x++,y++;
int curr=x;
for(int i=L-1;i>=0;i--)
if(jp[curr][i]<=y) curr=jp[curr][i];
int curr2=y;
for(int i=L-1;i>=0;i--)
if(jp[curr2][i]<=x+n) curr2=jp[curr2][i];
if(curr==y) return -1;
if(curr2==x+n) return 1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
