#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
pi t[mx*4];
int lz[mx*4];
void init(int n,int s,int e,vector<int>&v)
{
lz[n]=0;
if(s==e)
{
t[n]=pi(v[s],s);
return;
}
int m=s+(e-s)/2;
init(n*2,s,m,v);
init(n*2+1,m+1,e,v);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
inline void put(int n,int p)
{
t[n].fi+=p;
lz[n]+=p;
return;
}
inline void prop(int n)
{
if(lz[n]==0)
return;
put(n*2,lz[n]);
put(n*2+1,lz[n]);
lz[n]=0;
return;
}
void upd(int n,int s,int e,int S,int E,int p)
{
if(s>E||S>e)
return;
if(S<=s&&e<=E)
return put(n,p);
prop(n);
int m=s+(e-s)/2;
upd(n*2,s,m,S,E,p);
upd(n*2+1,m+1,e,S,E,p);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
}st1,st2;
struct seg2
{
int t[mx*4];
void init(int n,int s,int e,int v)
{
t[n]=v;
if(s==e)
return;
int m=s+(e-s)/2;
init(n*2,s,m,v);
init(n*2+1,m+1,e,v);
return;
}
void put(int n,int s,int e,int x,int p)
{
if(s==e)
{
t[n]=p;
return;
}
int m=s+(e-s)/2;
if(x>m)
put(n*2+1,m+1,e,x,p);
else
put(n*2,s,m,x,p);
t[n]=min(t[n*2],t[n*2+1]);
return;
}
int query(int n,int s,int e,int S,int E)
{
if(s>E||S>e)
return inf;
if(S<=s&&e<=E)
return t[n];
int m=s+(e-s)/2;
return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
}
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
n=r.size();
st1.init(1,0,n-1,r);
st2.init(1,0,n-1,r);
for(int i=0;i<n;i++)
{
while(st2.t[1].fi==0)
{
int cur=st2.t[1].se;
st2.upd(1,0,n-1,cur,cur,inf);
st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
}
int cur=st1.t[1].se;
ord[cur]=i;
ov.eb(cur);
st1.upd(1,0,n-1,cur,cur,inf);
st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
}
st3.init(1,0,n-1,n);
auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
st3.query(1,0,n-1,p-k+1+n,n-1));};
auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
st3.query(1,0,n-1,0,p+k-1-n));};
ov.eb(ord[n]=n);
for(int i=0;i<20;i++)
spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
for(int i=n;i-->0;)
{
int cur=ov[i];
int nx=ov[get3(cur)];
spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
nx=ov[get4(cur)];
spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
st3.put(1,0,n-1,cur,i);
}
for(int j=0;j<19;j++)
for(int i=0;i<=n;i++)
spa1[i][j+1]=spa1[spa1[i][j]][j],
spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
spa2[i][j+1]=spa2[spa2[i][j]][j],
spd2[i][j+1]=spd2[spa2[i][j]][j]+spd2[i][j];
return;
}
int compare_plants(int x,int y)
{
int p=1;
if(ord[x]>ord[y])
swap(x,y),p=-1;
int l=x,ld=0;
int r=x,rd=0;
for(int i=20;i-->0;)
if(ord[spa1[l][i]]<=ord[y])
ld+=spd1[l][i],l=spa1[l][i];
for(int i=20;i-->0;)
if(ord[spa2[r][i]]<=ord[y])
rd+=spd2[r][i],r=spa2[r][i];
l-=n*min(2,ld),r+=n*min(2,rd);
for(int i=-1;i<=1;i++)
if(l+i*n<=y&&y<=r+i*n)
return p;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
8 ms |
12928 KB |
Output is correct |
4 |
Correct |
9 ms |
12832 KB |
Output is correct |
5 |
Correct |
8 ms |
12928 KB |
Output is correct |
6 |
Correct |
91 ms |
15736 KB |
Output is correct |
7 |
Correct |
192 ms |
23220 KB |
Output is correct |
8 |
Correct |
795 ms |
87252 KB |
Output is correct |
9 |
Correct |
829 ms |
87312 KB |
Output is correct |
10 |
Correct |
869 ms |
87276 KB |
Output is correct |
11 |
Correct |
861 ms |
87348 KB |
Output is correct |
12 |
Correct |
904 ms |
87416 KB |
Output is correct |
13 |
Correct |
988 ms |
87404 KB |
Output is correct |
14 |
Correct |
944 ms |
87276 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
9 ms |
12928 KB |
Output is correct |
4 |
Correct |
8 ms |
12928 KB |
Output is correct |
5 |
Correct |
9 ms |
12928 KB |
Output is correct |
6 |
Correct |
15 ms |
13312 KB |
Output is correct |
7 |
Correct |
177 ms |
17656 KB |
Output is correct |
8 |
Correct |
11 ms |
13056 KB |
Output is correct |
9 |
Correct |
14 ms |
13312 KB |
Output is correct |
10 |
Correct |
179 ms |
17656 KB |
Output is correct |
11 |
Correct |
135 ms |
17528 KB |
Output is correct |
12 |
Correct |
140 ms |
17680 KB |
Output is correct |
13 |
Correct |
172 ms |
17784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
9 ms |
12928 KB |
Output is correct |
4 |
Correct |
8 ms |
12928 KB |
Output is correct |
5 |
Correct |
9 ms |
12928 KB |
Output is correct |
6 |
Correct |
15 ms |
13312 KB |
Output is correct |
7 |
Correct |
177 ms |
17656 KB |
Output is correct |
8 |
Correct |
11 ms |
13056 KB |
Output is correct |
9 |
Correct |
14 ms |
13312 KB |
Output is correct |
10 |
Correct |
179 ms |
17656 KB |
Output is correct |
11 |
Correct |
135 ms |
17528 KB |
Output is correct |
12 |
Correct |
140 ms |
17680 KB |
Output is correct |
13 |
Correct |
172 ms |
17784 KB |
Output is correct |
14 |
Correct |
361 ms |
23220 KB |
Output is correct |
15 |
Correct |
2486 ms |
87332 KB |
Output is correct |
16 |
Correct |
359 ms |
23348 KB |
Output is correct |
17 |
Correct |
2442 ms |
87496 KB |
Output is correct |
18 |
Correct |
1227 ms |
87424 KB |
Output is correct |
19 |
Correct |
1240 ms |
87492 KB |
Output is correct |
20 |
Correct |
2162 ms |
87440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
126 ms |
16376 KB |
Output is correct |
4 |
Correct |
1125 ms |
87560 KB |
Output is correct |
5 |
Correct |
1330 ms |
87404 KB |
Output is correct |
6 |
Correct |
1726 ms |
87444 KB |
Output is correct |
7 |
Correct |
2084 ms |
87416 KB |
Output is correct |
8 |
Correct |
2407 ms |
87676 KB |
Output is correct |
9 |
Correct |
1151 ms |
87532 KB |
Output is correct |
10 |
Correct |
1111 ms |
87456 KB |
Output is correct |
11 |
Correct |
958 ms |
87276 KB |
Output is correct |
12 |
Correct |
1054 ms |
87368 KB |
Output is correct |
13 |
Correct |
1259 ms |
87556 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
9 ms |
12928 KB |
Output is correct |
4 |
Correct |
8 ms |
12928 KB |
Output is correct |
5 |
Correct |
9 ms |
12928 KB |
Output is correct |
6 |
Correct |
12 ms |
13056 KB |
Output is correct |
7 |
Correct |
31 ms |
13568 KB |
Output is correct |
8 |
Correct |
31 ms |
13696 KB |
Output is correct |
9 |
Correct |
30 ms |
13696 KB |
Output is correct |
10 |
Correct |
32 ms |
13696 KB |
Output is correct |
11 |
Correct |
30 ms |
13696 KB |
Output is correct |
12 |
Correct |
29 ms |
13696 KB |
Output is correct |
13 |
Correct |
33 ms |
13696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
8 ms |
12928 KB |
Output is correct |
4 |
Correct |
10 ms |
12928 KB |
Output is correct |
5 |
Correct |
12 ms |
13184 KB |
Output is correct |
6 |
Correct |
1149 ms |
87352 KB |
Output is correct |
7 |
Correct |
1526 ms |
87600 KB |
Output is correct |
8 |
Correct |
1905 ms |
87480 KB |
Output is correct |
9 |
Correct |
2187 ms |
87400 KB |
Output is correct |
10 |
Correct |
1057 ms |
87416 KB |
Output is correct |
11 |
Correct |
1454 ms |
87288 KB |
Output is correct |
12 |
Correct |
986 ms |
87404 KB |
Output is correct |
13 |
Correct |
1258 ms |
87464 KB |
Output is correct |
14 |
Correct |
1518 ms |
87448 KB |
Output is correct |
15 |
Correct |
1941 ms |
87508 KB |
Output is correct |
16 |
Correct |
963 ms |
87224 KB |
Output is correct |
17 |
Correct |
1090 ms |
87268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12928 KB |
Output is correct |
2 |
Correct |
8 ms |
12928 KB |
Output is correct |
3 |
Correct |
8 ms |
12928 KB |
Output is correct |
4 |
Correct |
9 ms |
12832 KB |
Output is correct |
5 |
Correct |
8 ms |
12928 KB |
Output is correct |
6 |
Correct |
91 ms |
15736 KB |
Output is correct |
7 |
Correct |
192 ms |
23220 KB |
Output is correct |
8 |
Correct |
795 ms |
87252 KB |
Output is correct |
9 |
Correct |
829 ms |
87312 KB |
Output is correct |
10 |
Correct |
869 ms |
87276 KB |
Output is correct |
11 |
Correct |
861 ms |
87348 KB |
Output is correct |
12 |
Correct |
904 ms |
87416 KB |
Output is correct |
13 |
Correct |
988 ms |
87404 KB |
Output is correct |
14 |
Correct |
944 ms |
87276 KB |
Output is correct |
15 |
Correct |
9 ms |
12928 KB |
Output is correct |
16 |
Correct |
8 ms |
12928 KB |
Output is correct |
17 |
Correct |
9 ms |
12928 KB |
Output is correct |
18 |
Correct |
8 ms |
12928 KB |
Output is correct |
19 |
Correct |
9 ms |
12928 KB |
Output is correct |
20 |
Correct |
15 ms |
13312 KB |
Output is correct |
21 |
Correct |
177 ms |
17656 KB |
Output is correct |
22 |
Correct |
11 ms |
13056 KB |
Output is correct |
23 |
Correct |
14 ms |
13312 KB |
Output is correct |
24 |
Correct |
179 ms |
17656 KB |
Output is correct |
25 |
Correct |
135 ms |
17528 KB |
Output is correct |
26 |
Correct |
140 ms |
17680 KB |
Output is correct |
27 |
Correct |
172 ms |
17784 KB |
Output is correct |
28 |
Correct |
361 ms |
23220 KB |
Output is correct |
29 |
Correct |
2486 ms |
87332 KB |
Output is correct |
30 |
Correct |
359 ms |
23348 KB |
Output is correct |
31 |
Correct |
2442 ms |
87496 KB |
Output is correct |
32 |
Correct |
1227 ms |
87424 KB |
Output is correct |
33 |
Correct |
1240 ms |
87492 KB |
Output is correct |
34 |
Correct |
2162 ms |
87440 KB |
Output is correct |
35 |
Correct |
8 ms |
12928 KB |
Output is correct |
36 |
Correct |
8 ms |
12928 KB |
Output is correct |
37 |
Correct |
126 ms |
16376 KB |
Output is correct |
38 |
Correct |
1125 ms |
87560 KB |
Output is correct |
39 |
Correct |
1330 ms |
87404 KB |
Output is correct |
40 |
Correct |
1726 ms |
87444 KB |
Output is correct |
41 |
Correct |
2084 ms |
87416 KB |
Output is correct |
42 |
Correct |
2407 ms |
87676 KB |
Output is correct |
43 |
Correct |
1151 ms |
87532 KB |
Output is correct |
44 |
Correct |
1111 ms |
87456 KB |
Output is correct |
45 |
Correct |
958 ms |
87276 KB |
Output is correct |
46 |
Correct |
1054 ms |
87368 KB |
Output is correct |
47 |
Correct |
1259 ms |
87556 KB |
Output is correct |
48 |
Correct |
9 ms |
12928 KB |
Output is correct |
49 |
Correct |
8 ms |
12928 KB |
Output is correct |
50 |
Correct |
9 ms |
12928 KB |
Output is correct |
51 |
Correct |
8 ms |
12928 KB |
Output is correct |
52 |
Correct |
9 ms |
12928 KB |
Output is correct |
53 |
Correct |
12 ms |
13056 KB |
Output is correct |
54 |
Correct |
31 ms |
13568 KB |
Output is correct |
55 |
Correct |
31 ms |
13696 KB |
Output is correct |
56 |
Correct |
30 ms |
13696 KB |
Output is correct |
57 |
Correct |
32 ms |
13696 KB |
Output is correct |
58 |
Correct |
30 ms |
13696 KB |
Output is correct |
59 |
Correct |
29 ms |
13696 KB |
Output is correct |
60 |
Correct |
33 ms |
13696 KB |
Output is correct |
61 |
Correct |
109 ms |
16376 KB |
Output is correct |
62 |
Correct |
201 ms |
23092 KB |
Output is correct |
63 |
Correct |
917 ms |
87404 KB |
Output is correct |
64 |
Correct |
1152 ms |
87232 KB |
Output is correct |
65 |
Correct |
1615 ms |
87276 KB |
Output is correct |
66 |
Correct |
2035 ms |
87588 KB |
Output is correct |
67 |
Correct |
2444 ms |
87224 KB |
Output is correct |
68 |
Correct |
1103 ms |
87552 KB |
Output is correct |
69 |
Correct |
1638 ms |
87404 KB |
Output is correct |
70 |
Correct |
1130 ms |
87276 KB |
Output is correct |
71 |
Correct |
1286 ms |
87404 KB |
Output is correct |
72 |
Correct |
1701 ms |
87252 KB |
Output is correct |
73 |
Correct |
2099 ms |
87324 KB |
Output is correct |
74 |
Correct |
1002 ms |
87404 KB |
Output is correct |
75 |
Correct |
1183 ms |
87720 KB |
Output is correct |