#include <bits/stdc++.h>
#include "plants.h"
using namespace std;
typedef long long ll;
struct segTree{
pair<int, int> tree[1600002];
int lazy[1600002];
void init(int i, int l, int r, int *A){
lazy[i] = 0;
if(l==r){
tree[i] = make_pair(A[l], l);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
void propagate(int i, int l, int r){
tree[i].first += lazy[i];
if(l!=r){
lazy[i*2] += lazy[i];
lazy[i*2+1] += lazy[i];
}
lazy[i] = 0;
}
void add(int i, int l, int r, int s, int e, int val){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
lazy[i] += val;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
add(i*2, l, m, s, e, val);
add(i*2+1, m+1, r, s, e, val);
tree[i] = min(tree[i*2], tree[i*2+1]);
}
pair<int, int> findMin(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return make_pair(INT_MAX, INT_MAX);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return min(findMin(i*2, l, m, s, e), findMin(i*2+1, m+1, r, s, e));
}
} tree;
struct mineSeg{
struct Node {
ll lmax; int lidx;
ll rmax; int ridx;
ll ans; int ansl, ansr;
ll sum;
Node(){}
Node(ll x, int idx){
lmax = rmax = ans = sum = x;
lidx = ridx = ansl = ansr = idx;
}
Node merge(const Node &r)const{
Node ret = *this;
if(ret.lmax < sum + r.lmax){
ret.lmax = sum + r.lmax;
ret.lidx = r.lidx;
}
ret.rmax += r.sum;
if(ret.rmax < r.rmax){
ret.rmax = r.rmax;
ret.ridx = r.ridx;
}
if(ret.ans < r.ans) ret.ans = r.ans, ret.ansl = r.ansl, ret.ansr = r.ansr;
if(ret.ans < rmax + r.lmax){
ret.ans = rmax + r.lmax;
ret.ansl = ridx, ret.ansr = r.lidx;
}
ret.sum += r.sum;
return ret;
}
} tree[1600002];
void init(int i, int l, int r, int *A){
if(l==r){
tree[i] = Node(A[l] ? 1 : -1e9, l);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = tree[i*2].merge(tree[i*2+1]);
}
void change(int i, int l, int r, int idx, int x){
if(l==r){
tree[i] = Node(x ? 1 : -1e9, l);
return;
}
int m = (l+r)>>1;
if(idx <= m) change(i*2, l, m, idx, x);
else change(i*2+1, m+1, r, idx, x);
tree[i] = tree[i*2].merge(tree[i*2+1]);
}
} mineTree;
struct checkSeg{
ll MIN[1600002], MAX[1600002];
void init(int i, int l, int r){
if(l==r){
MIN[i] = 1e18;
MAX[i] = -1e18;
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
MIN[i] = min(MIN[i*2], MIN[i*2+1]);
MAX[i] = max(MAX[i*2], MAX[i*2+1]);
}
void update(int i, int l, int r, int idx, ll s, ll e){
if(l==r){
MIN[i] = s, MAX[i] = e;
return;
}
int m = (l+r)>>1;
if(idx <= m) update(i*2, l, m, idx, s, e);
else update(i*2+1, m+1, r, idx, s, e);
MIN[i] = min(MIN[i*2], MIN[i*2+1]);
MAX[i] = max(MAX[i*2], MAX[i*2+1]);
}
pair<ll, ll> query(int i, int l, int r, int s, int e){
if(r<s || e<l) return make_pair(1e18, -1e18);
if(s<=l && r<=e) return make_pair(MIN[i], MAX[i]);
int m = (l+r)>>1;
pair<ll, ll> p1 = query(i*2, l, m, s, e), p2 = query(i*2+1, m+1, r, s, e);
return make_pair(min(p1.first, p2.first), max(p1.second, p2.second));
}
} chkseg;
int n, k;
int arr[400002];
int sum[400002];
int ans[400002];
int ord[400002];
ll L[400002], R[400002];
void init(int _k, vector<int> r) {
n = (int)r.size();
k = _k;
for(int i=1; i<=n; i++) arr[i] = r[i-1];
for(int i=n+1; i<=n*2; i++) arr[i] = arr[i-n];
tree.init(1, 1, n*2, arr);
mineTree.init(1, 1, n*2, arr);
for(int turn=n; turn>=1; turn--){
auto tmp = mineTree.tree[1];
if(tmp.ans < k-1) exit(1);
int loc = tmp.ansr % n + 1;
ans[loc] = turn;
ord[turn] = loc;
/// 1에서 0이 되는 위치들을 검색
int lim = loc+n, leftmost = lim-k+1;
while(leftmost < lim){
pair<int, int> tmp2 = tree.findMin(1, 1, n*2, leftmost, lim-1);
if(tmp2.first > 1) break;
int x = tmp2.second;
mineTree.change(1, 1, n*2, (x-1)%n+1, 0);
mineTree.change(1, 1, n*2, (x-1)%n+1+n, 0);
leftmost = x+1;
}
mineTree.change(1, 1, n*2, loc, 1);
mineTree.change(1, 1, n*2, loc+n, 1);
/// tree 변경
tree.add(1, 1, n*2, loc, loc, 1000000000);
tree.add(1, 1, n*2, loc+n, loc+n, 1000000000);
if(loc >= k){
tree.add(1, 1, n*2, loc-k+1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
}
else{
tree.add(1, 1, n*2, 1, loc, -1);
tree.add(1, 1, n*2, loc-k+1+n, loc+n, -1);
tree.add(1, 1, n*2, 2*n-(k-loc)+1, n*2, -1);
}
}
chkseg.init(1, 1, n*2);
for(int turn=1; turn<=n; turn++){
int x = ord[turn];
chkseg.update(1, 1, n*2, x, x, x);
chkseg.update(1, 1, n*2, x+n, x+n, x+n);
L[x] = chkseg.query(1, 1, n*2, x+n-(k-1), x+n).first - n;
R[x] = chkseg.query(1, 1, n*2, x, x+(k-1)).second;
chkseg.update(1, 1, n*2, x, L[x], R[x]);
chkseg.update(1, 1, n*2, x+n, L[x]+n, R[x]+n);
}
}
int compare_plants(int x, int y) {
x++, y++;
int def = ans[x] > ans[y] ? 1 : -1;
if(ans[x] < ans[y]) swap(x, y);
ll l = L[x], r = R[x];
if((r-l) >= n) return def;
l = (n - (-l%n))%n;
if(!l) l=n;
r = (n - (-r%n))%n;
if(!r) r=n;
if(r<l) r+=n;
if(l<=y && y<=r) return def;
if(l<=y+n && y+n<=r) return def;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12852 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
6 ms |
12876 KB |
Output is correct |
4 |
Correct |
6 ms |
12876 KB |
Output is correct |
5 |
Correct |
6 ms |
12876 KB |
Output is correct |
6 |
Correct |
69 ms |
15704 KB |
Output is correct |
7 |
Correct |
147 ms |
26196 KB |
Output is correct |
8 |
Correct |
887 ms |
101032 KB |
Output is correct |
9 |
Correct |
880 ms |
101040 KB |
Output is correct |
10 |
Correct |
907 ms |
100936 KB |
Output is correct |
11 |
Correct |
860 ms |
100920 KB |
Output is correct |
12 |
Correct |
852 ms |
101016 KB |
Output is correct |
13 |
Correct |
809 ms |
101028 KB |
Output is correct |
14 |
Correct |
962 ms |
101080 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12876 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
6 ms |
12876 KB |
Output is correct |
4 |
Correct |
7 ms |
12876 KB |
Output is correct |
5 |
Correct |
7 ms |
12876 KB |
Output is correct |
6 |
Correct |
13 ms |
13188 KB |
Output is correct |
7 |
Correct |
95 ms |
18288 KB |
Output is correct |
8 |
Correct |
10 ms |
13004 KB |
Output is correct |
9 |
Correct |
14 ms |
13188 KB |
Output is correct |
10 |
Correct |
97 ms |
18372 KB |
Output is correct |
11 |
Correct |
85 ms |
18156 KB |
Output is correct |
12 |
Correct |
106 ms |
18372 KB |
Output is correct |
13 |
Correct |
95 ms |
18416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
12876 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
6 ms |
12876 KB |
Output is correct |
4 |
Correct |
7 ms |
12876 KB |
Output is correct |
5 |
Correct |
7 ms |
12876 KB |
Output is correct |
6 |
Correct |
13 ms |
13188 KB |
Output is correct |
7 |
Correct |
95 ms |
18288 KB |
Output is correct |
8 |
Correct |
10 ms |
13004 KB |
Output is correct |
9 |
Correct |
14 ms |
13188 KB |
Output is correct |
10 |
Correct |
97 ms |
18372 KB |
Output is correct |
11 |
Correct |
85 ms |
18156 KB |
Output is correct |
12 |
Correct |
106 ms |
18372 KB |
Output is correct |
13 |
Correct |
95 ms |
18416 KB |
Output is correct |
14 |
Correct |
222 ms |
26296 KB |
Output is correct |
15 |
Correct |
2397 ms |
101408 KB |
Output is correct |
16 |
Correct |
215 ms |
28612 KB |
Output is correct |
17 |
Correct |
2362 ms |
103840 KB |
Output is correct |
18 |
Correct |
1172 ms |
104020 KB |
Output is correct |
19 |
Correct |
1193 ms |
103952 KB |
Output is correct |
20 |
Correct |
2120 ms |
103860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12876 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
76 ms |
16360 KB |
Output is correct |
4 |
Correct |
1012 ms |
101060 KB |
Output is correct |
5 |
Correct |
1362 ms |
101308 KB |
Output is correct |
6 |
Correct |
1905 ms |
103808 KB |
Output is correct |
7 |
Correct |
2237 ms |
103988 KB |
Output is correct |
8 |
Correct |
2385 ms |
103952 KB |
Output is correct |
9 |
Correct |
1136 ms |
103932 KB |
Output is correct |
10 |
Correct |
1197 ms |
103832 KB |
Output is correct |
11 |
Correct |
794 ms |
103888 KB |
Output is correct |
12 |
Correct |
1033 ms |
103736 KB |
Output is correct |
13 |
Correct |
1132 ms |
103788 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12876 KB |
Output is correct |
2 |
Correct |
6 ms |
12992 KB |
Output is correct |
3 |
Correct |
6 ms |
12876 KB |
Output is correct |
4 |
Correct |
8 ms |
12876 KB |
Output is correct |
5 |
Incorrect |
7 ms |
12876 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12876 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
7 ms |
12876 KB |
Output is correct |
4 |
Correct |
7 ms |
12808 KB |
Output is correct |
5 |
Incorrect |
14 ms |
13236 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
12852 KB |
Output is correct |
2 |
Correct |
6 ms |
12876 KB |
Output is correct |
3 |
Correct |
6 ms |
12876 KB |
Output is correct |
4 |
Correct |
6 ms |
12876 KB |
Output is correct |
5 |
Correct |
6 ms |
12876 KB |
Output is correct |
6 |
Correct |
69 ms |
15704 KB |
Output is correct |
7 |
Correct |
147 ms |
26196 KB |
Output is correct |
8 |
Correct |
887 ms |
101032 KB |
Output is correct |
9 |
Correct |
880 ms |
101040 KB |
Output is correct |
10 |
Correct |
907 ms |
100936 KB |
Output is correct |
11 |
Correct |
860 ms |
100920 KB |
Output is correct |
12 |
Correct |
852 ms |
101016 KB |
Output is correct |
13 |
Correct |
809 ms |
101028 KB |
Output is correct |
14 |
Correct |
962 ms |
101080 KB |
Output is correct |
15 |
Correct |
8 ms |
12876 KB |
Output is correct |
16 |
Correct |
6 ms |
12876 KB |
Output is correct |
17 |
Correct |
6 ms |
12876 KB |
Output is correct |
18 |
Correct |
7 ms |
12876 KB |
Output is correct |
19 |
Correct |
7 ms |
12876 KB |
Output is correct |
20 |
Correct |
13 ms |
13188 KB |
Output is correct |
21 |
Correct |
95 ms |
18288 KB |
Output is correct |
22 |
Correct |
10 ms |
13004 KB |
Output is correct |
23 |
Correct |
14 ms |
13188 KB |
Output is correct |
24 |
Correct |
97 ms |
18372 KB |
Output is correct |
25 |
Correct |
85 ms |
18156 KB |
Output is correct |
26 |
Correct |
106 ms |
18372 KB |
Output is correct |
27 |
Correct |
95 ms |
18416 KB |
Output is correct |
28 |
Correct |
222 ms |
26296 KB |
Output is correct |
29 |
Correct |
2397 ms |
101408 KB |
Output is correct |
30 |
Correct |
215 ms |
28612 KB |
Output is correct |
31 |
Correct |
2362 ms |
103840 KB |
Output is correct |
32 |
Correct |
1172 ms |
104020 KB |
Output is correct |
33 |
Correct |
1193 ms |
103952 KB |
Output is correct |
34 |
Correct |
2120 ms |
103860 KB |
Output is correct |
35 |
Correct |
6 ms |
12876 KB |
Output is correct |
36 |
Correct |
6 ms |
12876 KB |
Output is correct |
37 |
Correct |
76 ms |
16360 KB |
Output is correct |
38 |
Correct |
1012 ms |
101060 KB |
Output is correct |
39 |
Correct |
1362 ms |
101308 KB |
Output is correct |
40 |
Correct |
1905 ms |
103808 KB |
Output is correct |
41 |
Correct |
2237 ms |
103988 KB |
Output is correct |
42 |
Correct |
2385 ms |
103952 KB |
Output is correct |
43 |
Correct |
1136 ms |
103932 KB |
Output is correct |
44 |
Correct |
1197 ms |
103832 KB |
Output is correct |
45 |
Correct |
794 ms |
103888 KB |
Output is correct |
46 |
Correct |
1033 ms |
103736 KB |
Output is correct |
47 |
Correct |
1132 ms |
103788 KB |
Output is correct |
48 |
Correct |
6 ms |
12876 KB |
Output is correct |
49 |
Correct |
6 ms |
12992 KB |
Output is correct |
50 |
Correct |
6 ms |
12876 KB |
Output is correct |
51 |
Correct |
8 ms |
12876 KB |
Output is correct |
52 |
Incorrect |
7 ms |
12876 KB |
Output isn't correct |
53 |
Halted |
0 ms |
0 KB |
- |