#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(),v.end()
#define SZ(a) ((int)a.size())
#define pb push_back
const int INF=1e9;
int Rtr[200005][20],Ltr[200005][20];
pii seg3[1600005],seg4[1600005];
int seg1[800005],seg2[800005],lazy1[800005],lazy2[800005];
int layer[400005];
vector<int> store[200005];
void build(int l,int r,int rt,const vector<int> &v,int *seg)
{
if(l==r)
return seg[rt]=v[l],void();
int mid=(l+r)>>1;
build(l,mid,rt<<1,v,seg),build(mid+1,r,rt<<1|1,v,seg);
seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}
void down(int rt,int *seg,int *lazy)
{
if(lazy[rt])
{
seg[rt<<1]+=lazy[rt],lazy[rt<<1]+=lazy[rt];
seg[rt<<1|1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
}
void modify(int L,int R,int l,int r,int rt,int val,int *seg,int *lazy)
{
if(l!=r) down(rt,seg,lazy);
if(L<=l&&R>=r)
return lazy[rt]+=val,seg[rt]+=val,void();
int mid=(l+r)>>1;
if(L<=mid)
modify(L,R,l,mid,rt<<1,val,seg,lazy);
if(R>mid)
modify(L,R,mid+1,r,rt<<1|1,val,seg,lazy);
seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}
int query(int l,int r,int rt,int *seg,int *lazy)
{
if(l!=r) down(rt,seg,lazy);
if(l==r)
return l;
int mid=(l+r)>>1;
if(seg[rt<<1]<=seg[rt<<1|1])
return query(l,mid,rt<<1,seg,lazy);
return query(mid+1,r,rt<<1|1,seg,lazy);
}
void dfs(int l,int r,int rt,int *seg,int *lazy,vector<int> &rst)
{
if(l!=r) down(rt,seg,lazy);
if(l==r)
return rst.pb(l);
int mid=(l+r)>>1;
if(seg[rt<<1]==0)
dfs(l,mid,rt<<1,seg,lazy,rst);
if(seg[rt<<1|1]==0)
dfs(mid+1,r,rt<<1|1,seg,lazy,rst);
}
void build3(int l,int r,int rt)
{
seg3[rt]=pii(INF,l);
if(l==r)
return;
int mid=(l+r)>>1;
build3(l,mid,rt<<1),build3(mid+1,r,rt<<1|1);
}
void build4(int l,int r,int rt)
{
seg4[rt]=pii(INF,-r);
if(l==r)
return;
int mid=(l+r)>>1;
build4(l,mid,rt<<1),build4(mid+1,r,rt<<1|1);
}
void modify3(int x,int l,int r,int rt,int val)
{
if(l==r)
return seg3[rt]=pii(val,l),void();
int mid=(l+r)>>1;
if(x<=mid)
modify3(x,l,mid,rt<<1,val);
else
modify3(x,mid+1,r,rt<<1|1,val);
seg3[rt]=min(seg3[rt<<1],seg3[rt<<1|1]);
}
void modify4(int x,int l,int r,int rt,int val)
{
if(l==r)
return seg4[rt]=pii(val,-r),void();
int mid=(l+r)>>1;
if(x<=mid)
modify4(x,l,mid,rt<<1,val);
else
modify4(x,mid+1,r,rt<<1|1,val);
seg4[rt]=min(seg4[rt<<1],seg4[rt<<1|1]);
}
pii query2(int L,int R,int l,int r,int rt,pii *seg)
{
if(L<=l&&R>=r)
return seg[rt];
int mid=(l+r)>>1;
if(R<=mid)
return query2(L,R,l,mid,rt<<1,seg);
if(L>mid)
return query2(L,R,mid+1,r,rt<<1|1,seg);
return min(query2(L,R,l,mid,rt<<1,seg),query2(L,R,mid+1,r,rt<<1|1,seg));
}
int arr[200005],K,n,L;
void init(int k, vector<int> r)
{
n=SZ(r),K=k,L=__lg(n);
if(n>300) exit(0);
int ly=0;
build(0,n-1,1,r,seg1),build(0,n-1,1,vector<int>(n,INF),seg2);
for(int i=0;i<n;++ly)
{
while(seg1[1]==0)
{
int u=query(0,n-1,1,seg1,lazy1);
modify(u,u,0,n-1,1,INF,seg1,lazy1),modify(u,u,0,n-1,1,-INF,seg2,lazy2);
if(u+k<=n)
modify(u+1,u+k-1,0,n-1,1,1,seg2,lazy2);
else
{
if(u<n-1)
modify(u+1,n-1,0,n-1,1,1,seg2,lazy2);
modify(0,k-n+u-1,0,n-1,1,1,seg2,lazy2);
}
}
vector<int> rst;
dfs(0,n-1,1,seg2,lazy2,rst);
for(int u:rst)
{
if(u>=k-1)
modify(u-k+1,u,0,n-1,1,-1,seg1,lazy1);
else
modify(0,u,0,n-1,1,-1,seg1,lazy1),modify(n-(k-u-1),n-1,0,n-1,1,-1,seg1,lazy1);
if(u+k<=n)
modify(u+1,u+k-1,0,n-1,1,-1,seg2,lazy2);
else
{
if(u<n-1)
modify(u+1,n-1,0,n-1,1,-1,seg2,lazy2);
modify(0,k-n+u-1,0,n-1,1,-1,seg2,lazy2);
}
modify(u,u,0,n-1,1,INF,seg2,lazy2);
layer[u]=ly;
}
i+=SZ(rst),store[ly].swap(rst);
}
for(int i=0;i<n;++i)
layer[i+n]=layer[i];
build3(0,2*n-1,1),build4(0,2*n-1,1);
for(int i=ly-1;i>=0;--i)
{
for(int u:store[i])
{
pii tmp=query2(u+n-k+1,u+n,0,2*n-1,1,seg3);
if(tmp.X==INF)
Ltr[u][0]=u;
else
Ltr[u][0]=tmp.Y%n;
tmp=query2(u,u+k-1,0,2*n-1,1,seg4);
if(tmp.X==INF)
Rtr[u][0]=u;
else
Rtr[u][0]=(-tmp.Y)%n;
}
for(int u:store[i])
modify3(u,0,2*n-1,1,layer[u]),modify3(u+n,0,2*n-1,1,layer[u]),
modify4(u,0,2*n-1,1,layer[u]),modify4(u+n,0,2*n-1,1,layer[u]);
}
for(int t=1;t<=L;++t)
for(int i=0;i<n;++i)
Ltr[i][t]=Ltr[Ltr[i][t-1]][t-1],Rtr[i][t]=Rtr[Rtr[i][t-1]][t-1];
/*cout << "layer: ";
for(int i=0;i<n;++i)
cout << layer[i] << " ";
cout << endl;
cout << "Ltr: ";
for(int i=0;i<n;++i)
cout << Ltr[i][0] << " ";
cout << endl;
cout << "Rtr: ";
for(int i=0;i<n;++i)
cout << Rtr[i][0] << " ";
cout << endl;*/
}
int compare_plants(int x, int y)
{
if(layer[x]==layer[y]) return 0;
int rt=1,tar,nw;
if(layer[x]>layer[y])
swap(x,y),rt=-1;
if(x>y)
tar=y+n;
else
tar=y;
nw=x;
if(nw+K>tar)
return rt;
for(int i=L;i>=0;--i)
if(Rtr[nw][i]+(Rtr[nw][i]<x)*n+K<=tar)
nw=Rtr[nw][i];
nw=Rtr[nw][0];
if(layer[y]>layer[nw]&&nw+(nw<x)*n+K>tar)
return rt;
nw=x;
if(x<y)
tar=y-n;
else
tar=y;
if(nw-K<tar)
return rt;
for(int i=L;i>=0;--i)
if(Ltr[nw][i]-(Ltr[nw][i]>x)*n-K>=tar)
nw=Ltr[nw][i];
nw=Ltr[nw][0];
if(layer[y]>layer[nw]&&nw-(nw>x)*n-K<tar)
return rt;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
3 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
76 ms |
7932 KB |
Output is correct |
7 |
Incorrect |
63 ms |
7544 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Incorrect |
5 ms |
5120 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Incorrect |
58 ms |
7424 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
5 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
6 ms |
5120 KB |
Output is correct |
7 |
Correct |
24 ms |
5760 KB |
Output is correct |
8 |
Incorrect |
22 ms |
5888 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Incorrect |
4 ms |
4992 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
3 ms |
5120 KB |
Output is correct |
3 |
Correct |
4 ms |
5120 KB |
Output is correct |
4 |
Correct |
4 ms |
5120 KB |
Output is correct |
5 |
Correct |
4 ms |
5120 KB |
Output is correct |
6 |
Correct |
76 ms |
7932 KB |
Output is correct |
7 |
Incorrect |
63 ms |
7544 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |