#include "plants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": "; for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int)x.size())
const int inf=1000000100; // 1e9
const ll INF=10000000001000000; // 1e16
const int mod=1000000007;
const int MAXN=200010, LOG=18;
int n, m, k, x, y, u, v, t, a, b, posmx;
int A[MAXN], B[MAXN];
int mark1[MAXN], mark2[MAXN];
int L[LOG][MAXN], R[LOG][MAXN];
vector<int> G[MAXN], GR[MAXN];
struct Segment{
pii seg[MAXN<<2];
int lazy[MAXN<<2];
pii Build(int id, int tl, int tr, int *A){
if (tr-tl==1) return seg[id]={A[tl], tl};
int mid=(tl+tr)>>1;
return seg[id]=min(Build(id<<1, tl, mid, A), Build(id<<1 | 1, mid, tr, A));
}
inline void add_lazy(int id, int val){
seg[id].first+=val;
lazy[id]+=val;
}
inline void shift(int id){
if (lazy[id]){
add_lazy(id<<1, lazy[id]);
add_lazy(id<<1 | 1, lazy[id]);
lazy[id]=0;
}
}
void Add(int id, int tl, int tr, int l, int r, int val){
if (r<=tl || tr<=l) return ;
if (l<=tl && tr<=r){
add_lazy(id, val);
return ;
}
shift(id);
int mid=(tl+tr)>>1;
Add(id<<1, tl, mid, l, r, val);
Add(id<<1 | 1, mid, tr, l, r, val);
seg[id]=min(seg[id<<1], seg[id<<1 | 1]);
}
pii Get(int id, int tl, int tr, int l, int r){
if (r<=tl || tr<=l) return {inf, 0};
if (l<=tl && tr<=r) return seg[id];
shift(id);
int mid=(tl+tr)>>1;
return min(Get(id<<1, tl, mid, l, r), Get(id<<1 | 1, mid, tr, l, r));
}
} seg1, seg2, seg3;
void relax(){
while (!seg1.seg[1].first){
int mx=seg1.seg[1].second;
// cerr<<mx<<" became 0\n";
seg1.Add(1, 0, n, mx, mx+1, inf);
seg2.Add(1, 0, n, mx, mx+1, -inf);
seg2.Add(1, 0, n, mx+1, mx+k, +1);
seg2.Add(1, 0, n, 0, mx+k-n, +1);
}
}
inline void add_edge(int u, int v){
G[u].pb(v);
GR[v].pb(u);
}
void init(int _k, vi _A){
n=SZ(_A);
k=_k;
for (int i=0; i<n; i++) A[i]=_A[i];
seg1.Build(1, 0, n, A);
seg2.Build(1, 0, n, B); // any empty array
seg3.Build(1, 0, n, B);
seg2.Add(1, 0, n, 0, n, inf);
seg3.Add(1, 0, n, 0, n, inf);
relax();
for (int i=0; i<n; i++){
int mx=seg2.seg[1].second;
B[mx]=n-i;
seg2.Add(1, 0, n, mx, mx+1, inf);
seg2.Add(1, 0, n, mx+1, mx+k, -1);
seg2.Add(1, 0, n, 0, mx+k-n, -1);
seg1.Add(1, 0, n, mx-k+1, mx, -1);
seg1.Add(1, 0, n, n+mx-k+1, n, -1);
relax();
seg3.Add(1, 0, n, mx, mx+1, -inf+B[mx]);
pii l=min(seg3.Get(1, 0, n, mx-k+1, mx), seg3.Get(1, 0, n, mx-k+1+n, n));
pii r=min(seg3.Get(1, 0, n, mx+1, mx+k), seg3.Get(1, 0, n, 0, mx+k-n));
if (l.first<inf) L[0][mx]=(n+mx-l.second)%n; //add_edge(mx, l.second);
if (r.first<inf) R[0][mx]=(r.second-mx+n)%n; //add_edge(mx, r.second);
}
// for (int i=0; i<n; i++) cerr<<B[i]-1<<" \n"[i==n-1];
for (int j=1; j<LOG; j++) for (int i=0; i<n; i++){
L[j][i]=L[j-1][i] + L[j-1][(i-L[j-1][i])%n];
R[j][i]=R[j-1][i] + R[j-1][(i+R[j-1][i])%n];
}
return ;
}
int compare_plants(int x, int y){
if (B[x]>B[y]) return -compare_plants(y, x);
int l=x, dl=(x-y+n)%n;
int r=x, dr=(y-x+n)%n;
for (int i=LOG-1; ~i; i--){
if (L[i][l]<=dl){
dl-=L[i][l];
l=(l-L[i][l]+n)%n;
}
if (R[i][r]<=dr){
dr-=R[i][r];
r=(r+R[i][r]+n)%n;
}
}
if (B[l]<=B[y] && dl<k) return -1;
if (B[r]<=B[y] && dr<k) return -1;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
28704 KB |
Output is correct |
2 |
Correct |
16 ms |
28624 KB |
Output is correct |
3 |
Correct |
16 ms |
28620 KB |
Output is correct |
4 |
Correct |
16 ms |
28656 KB |
Output is correct |
5 |
Correct |
16 ms |
28668 KB |
Output is correct |
6 |
Correct |
113 ms |
32496 KB |
Output is correct |
7 |
Correct |
218 ms |
37436 KB |
Output is correct |
8 |
Correct |
1085 ms |
70596 KB |
Output is correct |
9 |
Correct |
1053 ms |
70596 KB |
Output is correct |
10 |
Correct |
1080 ms |
70460 KB |
Output is correct |
11 |
Correct |
1026 ms |
69968 KB |
Output is correct |
12 |
Correct |
1010 ms |
69828 KB |
Output is correct |
13 |
Correct |
1053 ms |
69912 KB |
Output is correct |
14 |
Correct |
1031 ms |
69920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28664 KB |
Output is correct |
2 |
Correct |
15 ms |
28632 KB |
Output is correct |
3 |
Correct |
15 ms |
28716 KB |
Output is correct |
4 |
Correct |
15 ms |
28640 KB |
Output is correct |
5 |
Correct |
16 ms |
28748 KB |
Output is correct |
6 |
Correct |
21 ms |
28876 KB |
Output is correct |
7 |
Correct |
118 ms |
32916 KB |
Output is correct |
8 |
Correct |
17 ms |
28748 KB |
Output is correct |
9 |
Correct |
20 ms |
29004 KB |
Output is correct |
10 |
Correct |
114 ms |
32860 KB |
Output is correct |
11 |
Correct |
138 ms |
32836 KB |
Output is correct |
12 |
Correct |
151 ms |
32980 KB |
Output is correct |
13 |
Correct |
112 ms |
32932 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28664 KB |
Output is correct |
2 |
Correct |
15 ms |
28632 KB |
Output is correct |
3 |
Correct |
15 ms |
28716 KB |
Output is correct |
4 |
Correct |
15 ms |
28640 KB |
Output is correct |
5 |
Correct |
16 ms |
28748 KB |
Output is correct |
6 |
Correct |
21 ms |
28876 KB |
Output is correct |
7 |
Correct |
118 ms |
32916 KB |
Output is correct |
8 |
Correct |
17 ms |
28748 KB |
Output is correct |
9 |
Correct |
20 ms |
29004 KB |
Output is correct |
10 |
Correct |
114 ms |
32860 KB |
Output is correct |
11 |
Correct |
138 ms |
32836 KB |
Output is correct |
12 |
Correct |
151 ms |
32980 KB |
Output is correct |
13 |
Correct |
112 ms |
32932 KB |
Output is correct |
14 |
Correct |
194 ms |
35808 KB |
Output is correct |
15 |
Incorrect |
1966 ms |
68756 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
28652 KB |
Output is correct |
2 |
Correct |
15 ms |
28620 KB |
Output is correct |
3 |
Correct |
122 ms |
32280 KB |
Output is correct |
4 |
Correct |
1060 ms |
68584 KB |
Output is correct |
5 |
Incorrect |
1214 ms |
68836 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28620 KB |
Output is correct |
2 |
Correct |
15 ms |
28628 KB |
Output is correct |
3 |
Correct |
16 ms |
28624 KB |
Output is correct |
4 |
Correct |
15 ms |
28620 KB |
Output is correct |
5 |
Correct |
16 ms |
28712 KB |
Output is correct |
6 |
Correct |
19 ms |
28768 KB |
Output is correct |
7 |
Correct |
46 ms |
29604 KB |
Output is correct |
8 |
Correct |
33 ms |
29644 KB |
Output is correct |
9 |
Correct |
44 ms |
29588 KB |
Output is correct |
10 |
Correct |
35 ms |
29640 KB |
Output is correct |
11 |
Correct |
40 ms |
29624 KB |
Output is correct |
12 |
Correct |
37 ms |
29636 KB |
Output is correct |
13 |
Correct |
32 ms |
29616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
28592 KB |
Output is correct |
2 |
Correct |
15 ms |
28660 KB |
Output is correct |
3 |
Correct |
15 ms |
28600 KB |
Output is correct |
4 |
Correct |
15 ms |
28620 KB |
Output is correct |
5 |
Correct |
19 ms |
28876 KB |
Output is correct |
6 |
Incorrect |
909 ms |
70604 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
28704 KB |
Output is correct |
2 |
Correct |
16 ms |
28624 KB |
Output is correct |
3 |
Correct |
16 ms |
28620 KB |
Output is correct |
4 |
Correct |
16 ms |
28656 KB |
Output is correct |
5 |
Correct |
16 ms |
28668 KB |
Output is correct |
6 |
Correct |
113 ms |
32496 KB |
Output is correct |
7 |
Correct |
218 ms |
37436 KB |
Output is correct |
8 |
Correct |
1085 ms |
70596 KB |
Output is correct |
9 |
Correct |
1053 ms |
70596 KB |
Output is correct |
10 |
Correct |
1080 ms |
70460 KB |
Output is correct |
11 |
Correct |
1026 ms |
69968 KB |
Output is correct |
12 |
Correct |
1010 ms |
69828 KB |
Output is correct |
13 |
Correct |
1053 ms |
69912 KB |
Output is correct |
14 |
Correct |
1031 ms |
69920 KB |
Output is correct |
15 |
Correct |
15 ms |
28664 KB |
Output is correct |
16 |
Correct |
15 ms |
28632 KB |
Output is correct |
17 |
Correct |
15 ms |
28716 KB |
Output is correct |
18 |
Correct |
15 ms |
28640 KB |
Output is correct |
19 |
Correct |
16 ms |
28748 KB |
Output is correct |
20 |
Correct |
21 ms |
28876 KB |
Output is correct |
21 |
Correct |
118 ms |
32916 KB |
Output is correct |
22 |
Correct |
17 ms |
28748 KB |
Output is correct |
23 |
Correct |
20 ms |
29004 KB |
Output is correct |
24 |
Correct |
114 ms |
32860 KB |
Output is correct |
25 |
Correct |
138 ms |
32836 KB |
Output is correct |
26 |
Correct |
151 ms |
32980 KB |
Output is correct |
27 |
Correct |
112 ms |
32932 KB |
Output is correct |
28 |
Correct |
194 ms |
35808 KB |
Output is correct |
29 |
Incorrect |
1966 ms |
68756 KB |
Output isn't correct |
30 |
Halted |
0 ms |
0 KB |
- |