#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;
struct node
{
int pa;
ll dis;
node operator+(const node &a)const{
return node{a.pa,dis+a.dis};
}
}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);
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]=node{u,0};
else
Ltr[u][0]=node{tmp.Y%n,u+n-tmp.Y};
tmp=query2(u,u+k-1,0,2*n-1,1,seg4);
if(tmp.X==INF)
Rtr[u][0]=node{u,0};
else
Rtr[u][0]=node{(-tmp.Y)%n,(-tmp.Y)-u};
}
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[i][t-1]+Ltr[Ltr[i][t-1].pa][t-1],Rtr[i][t]=Rtr[i][t-1]+Rtr[Rtr[i][t-1].pa][t-1];
}
int compare_plants(int x, int y)
{
if(layer[x]==layer[y]) return 0;
int rt=1,tar,nw;
ll dis;
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;
dis=0;
for(int i=L;i>=0;--i)
if(x+dis+Rtr[nw][i].dis+K<=tar)
dis+=Rtr[nw][i].dis,nw=Rtr[nw][i].pa;
dis+=Rtr[nw][0].dis,nw=Rtr[nw][0].pa;
if(layer[y]>layer[nw]&&x+dis+K>tar)
return rt;
nw=x;
if(x<y)
tar=y-n;
else
tar=y;
if(nw-K<tar)
return rt;
dis=0;
for(int i=L;i>=0;--i)
if(x+dis-Ltr[nw][i].dis-K>=tar)
dis-=Ltr[nw][i].dis,nw=Ltr[nw][i].pa;
dis-=Ltr[nw][0].dis,nw=Ltr[nw][0].pa;
if(layer[y]>layer[nw]&&x+dis-K<tar)
return rt;
return 0;
}
# |
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 |
Correct |
76 ms |
7928 KB |
Output is correct |
7 |
Correct |
227 ms |
23904 KB |
Output is correct |
8 |
Correct |
1103 ms |
160360 KB |
Output is correct |
9 |
Correct |
1204 ms |
160664 KB |
Output is correct |
10 |
Correct |
1172 ms |
160616 KB |
Output is correct |
11 |
Correct |
1101 ms |
161128 KB |
Output is correct |
12 |
Correct |
1094 ms |
162792 KB |
Output is correct |
13 |
Correct |
1132 ms |
165860 KB |
Output is correct |
14 |
Correct |
1200 ms |
165756 KB |
Output is correct |
# |
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 |
Correct |
10 ms |
5888 KB |
Output is correct |
7 |
Correct |
104 ms |
12056 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
10 ms |
5888 KB |
Output is correct |
10 |
Correct |
105 ms |
12024 KB |
Output is correct |
11 |
Correct |
103 ms |
12024 KB |
Output is correct |
12 |
Correct |
102 ms |
12152 KB |
Output is correct |
13 |
Correct |
100 ms |
12024 KB |
Output is correct |
# |
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 |
Correct |
10 ms |
5888 KB |
Output is correct |
7 |
Correct |
104 ms |
12056 KB |
Output is correct |
8 |
Correct |
6 ms |
5248 KB |
Output is correct |
9 |
Correct |
10 ms |
5888 KB |
Output is correct |
10 |
Correct |
105 ms |
12024 KB |
Output is correct |
11 |
Correct |
103 ms |
12024 KB |
Output is correct |
12 |
Correct |
102 ms |
12152 KB |
Output is correct |
13 |
Correct |
100 ms |
12024 KB |
Output is correct |
14 |
Correct |
222 ms |
24540 KB |
Output is correct |
15 |
Correct |
2044 ms |
166760 KB |
Output is correct |
16 |
Correct |
223 ms |
24444 KB |
Output is correct |
17 |
Correct |
2049 ms |
166736 KB |
Output is correct |
18 |
Correct |
1308 ms |
166756 KB |
Output is correct |
19 |
Correct |
1259 ms |
166888 KB |
Output is correct |
20 |
Correct |
1864 ms |
166760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5120 KB |
Output is correct |
2 |
Correct |
4 ms |
5152 KB |
Output is correct |
3 |
Correct |
129 ms |
9448 KB |
Output is correct |
4 |
Correct |
1247 ms |
164436 KB |
Output is correct |
5 |
Correct |
1405 ms |
162148 KB |
Output is correct |
6 |
Correct |
1828 ms |
162920 KB |
Output is correct |
7 |
Correct |
1962 ms |
163792 KB |
Output is correct |
8 |
Correct |
2001 ms |
166552 KB |
Output is correct |
9 |
Correct |
1242 ms |
161896 KB |
Output is correct |
10 |
Correct |
1238 ms |
165608 KB |
Output is correct |
11 |
Correct |
1110 ms |
165700 KB |
Output is correct |
12 |
Correct |
1322 ms |
166876 KB |
Output is correct |
13 |
Correct |
1346 ms |
166628 KB |
Output is correct |
# |
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 |
Correct |
6 ms |
5248 KB |
Output is correct |
7 |
Correct |
24 ms |
6008 KB |
Output is correct |
8 |
Correct |
24 ms |
6016 KB |
Output is correct |
9 |
Correct |
25 ms |
6008 KB |
Output is correct |
10 |
Correct |
22 ms |
6016 KB |
Output is correct |
11 |
Correct |
24 ms |
6008 KB |
Output is correct |
12 |
Correct |
26 ms |
6016 KB |
Output is correct |
13 |
Correct |
20 ms |
6016 KB |
Output is correct |
# |
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 |
8 ms |
5888 KB |
Output is correct |
6 |
Correct |
1557 ms |
161664 KB |
Output is correct |
7 |
Correct |
1774 ms |
161768 KB |
Output is correct |
8 |
Correct |
1900 ms |
161896 KB |
Output is correct |
9 |
Correct |
2020 ms |
166120 KB |
Output is correct |
10 |
Correct |
1072 ms |
161896 KB |
Output is correct |
11 |
Correct |
1580 ms |
163688 KB |
Output is correct |
12 |
Correct |
1100 ms |
164448 KB |
Output is correct |
13 |
Correct |
1314 ms |
162664 KB |
Output is correct |
14 |
Correct |
1713 ms |
163052 KB |
Output is correct |
15 |
Correct |
1905 ms |
163688 KB |
Output is correct |
16 |
Correct |
1132 ms |
165096 KB |
Output is correct |
17 |
Correct |
1223 ms |
163448 KB |
Output is correct |
# |
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 |
Correct |
76 ms |
7928 KB |
Output is correct |
7 |
Correct |
227 ms |
23904 KB |
Output is correct |
8 |
Correct |
1103 ms |
160360 KB |
Output is correct |
9 |
Correct |
1204 ms |
160664 KB |
Output is correct |
10 |
Correct |
1172 ms |
160616 KB |
Output is correct |
11 |
Correct |
1101 ms |
161128 KB |
Output is correct |
12 |
Correct |
1094 ms |
162792 KB |
Output is correct |
13 |
Correct |
1132 ms |
165860 KB |
Output is correct |
14 |
Correct |
1200 ms |
165756 KB |
Output is correct |
15 |
Correct |
4 ms |
5120 KB |
Output is correct |
16 |
Correct |
4 ms |
5120 KB |
Output is correct |
17 |
Correct |
4 ms |
5120 KB |
Output is correct |
18 |
Correct |
4 ms |
5120 KB |
Output is correct |
19 |
Correct |
4 ms |
5120 KB |
Output is correct |
20 |
Correct |
10 ms |
5888 KB |
Output is correct |
21 |
Correct |
104 ms |
12056 KB |
Output is correct |
22 |
Correct |
6 ms |
5248 KB |
Output is correct |
23 |
Correct |
10 ms |
5888 KB |
Output is correct |
24 |
Correct |
105 ms |
12024 KB |
Output is correct |
25 |
Correct |
103 ms |
12024 KB |
Output is correct |
26 |
Correct |
102 ms |
12152 KB |
Output is correct |
27 |
Correct |
100 ms |
12024 KB |
Output is correct |
28 |
Correct |
222 ms |
24540 KB |
Output is correct |
29 |
Correct |
2044 ms |
166760 KB |
Output is correct |
30 |
Correct |
223 ms |
24444 KB |
Output is correct |
31 |
Correct |
2049 ms |
166736 KB |
Output is correct |
32 |
Correct |
1308 ms |
166756 KB |
Output is correct |
33 |
Correct |
1259 ms |
166888 KB |
Output is correct |
34 |
Correct |
1864 ms |
166760 KB |
Output is correct |
35 |
Correct |
4 ms |
5120 KB |
Output is correct |
36 |
Correct |
4 ms |
5152 KB |
Output is correct |
37 |
Correct |
129 ms |
9448 KB |
Output is correct |
38 |
Correct |
1247 ms |
164436 KB |
Output is correct |
39 |
Correct |
1405 ms |
162148 KB |
Output is correct |
40 |
Correct |
1828 ms |
162920 KB |
Output is correct |
41 |
Correct |
1962 ms |
163792 KB |
Output is correct |
42 |
Correct |
2001 ms |
166552 KB |
Output is correct |
43 |
Correct |
1242 ms |
161896 KB |
Output is correct |
44 |
Correct |
1238 ms |
165608 KB |
Output is correct |
45 |
Correct |
1110 ms |
165700 KB |
Output is correct |
46 |
Correct |
1322 ms |
166876 KB |
Output is correct |
47 |
Correct |
1346 ms |
166628 KB |
Output is correct |
48 |
Correct |
4 ms |
5120 KB |
Output is correct |
49 |
Correct |
4 ms |
5120 KB |
Output is correct |
50 |
Correct |
4 ms |
5120 KB |
Output is correct |
51 |
Correct |
4 ms |
5120 KB |
Output is correct |
52 |
Correct |
4 ms |
5120 KB |
Output is correct |
53 |
Correct |
6 ms |
5248 KB |
Output is correct |
54 |
Correct |
24 ms |
6008 KB |
Output is correct |
55 |
Correct |
24 ms |
6016 KB |
Output is correct |
56 |
Correct |
25 ms |
6008 KB |
Output is correct |
57 |
Correct |
22 ms |
6016 KB |
Output is correct |
58 |
Correct |
24 ms |
6008 KB |
Output is correct |
59 |
Correct |
26 ms |
6016 KB |
Output is correct |
60 |
Correct |
20 ms |
6016 KB |
Output is correct |
61 |
Correct |
105 ms |
9336 KB |
Output is correct |
62 |
Correct |
222 ms |
23928 KB |
Output is correct |
63 |
Correct |
1245 ms |
161204 KB |
Output is correct |
64 |
Correct |
1631 ms |
161564 KB |
Output is correct |
65 |
Correct |
1995 ms |
162116 KB |
Output is correct |
66 |
Correct |
1998 ms |
162020 KB |
Output is correct |
67 |
Correct |
2058 ms |
166276 KB |
Output is correct |
68 |
Correct |
1199 ms |
162024 KB |
Output is correct |
69 |
Correct |
1695 ms |
163728 KB |
Output is correct |
70 |
Correct |
1249 ms |
163728 KB |
Output is correct |
71 |
Correct |
1415 ms |
162408 KB |
Output is correct |
72 |
Correct |
1861 ms |
163176 KB |
Output is correct |
73 |
Correct |
2004 ms |
163940 KB |
Output is correct |
74 |
Correct |
1397 ms |
161384 KB |
Output is correct |
75 |
Correct |
1265 ms |
166148 KB |
Output is correct |