// plants-yanhao-ac
class segtree {
final int n_bits=18;
final int inf = (int)1e9;
int[] arr = new int [1<<(n_bits+1)];
int[] lazyadd = new int [1<<(n_bits+1)];
int node = 1;
int lazy = 0;
int low(int i) {
return (i<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits);
}
int high(int i) {
return ((i+1)<<(Integer.numberOfLeadingZeros(i)-31+n_bits))-(1<<n_bits)-1;
}
void build(int[] v) {
assert(v.length<(1<<n_bits));
for(int i=0; i<(1<<n_bits); i++) {
arr[i+(1<<n_bits)] = (i<v.length ? v[i] : inf);
}
for(int i=(1<<n_bits)-1; i>=1; i--) {
arr[i] = Math.min(arr[2*i], arr[2*i+1]);
}
for(int i=0; i<(1<<(n_bits+1)); i++) {
lazyadd[i] = 0;
}
}
void decr(int left, int right) {
node = 1;
while(node != 0) {
if(right>=high(node) && left<=low(node)) {
lazyadd[node]--;
while(node%2==0) {
arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
node = node/2;
}
node--;
} else if(right<low(node) || left>high(node)) {
while(node%2==0) {
arr[node/2] = Math.min(arr[node]+lazyadd[node], arr[node+1]+lazyadd[node+1]);
node = node/2;
}
node--;
} else {
node = node*2+1;
}
}
}
void pt_update(int x) {
x += (1<<n_bits);
arr[x] = (int)1e9;
while(x!=0) {
arr[x/2] = Math.min(arr[x]+lazyadd[x], arr[x^1]+lazyadd[x^1]);
x = x/2;
}
}
int find_zero() {
node = 1;
lazy = 0;
if(lazyadd[1] + arr[1]!=0) return -1;
while(node < (1<<n_bits)) {
lazy += lazyadd[node];
node *= 2;
if(lazy + lazyadd[node] + arr[node] != 0) node++;
}
return node-(1<<n_bits);
}
};
class plants {
final int n_max = (int)2e5+5;
int[] p_lt = new int[n_max];
int[] p_rg = new int[n_max];
int[] stash = new int[n_max]; // a manual queue
int[] tallest = new int[n_max];
int[] shortest = new int[n_max];
void lexi_smallest(int k, int[] r, int[] ptr, int[] ord) {
segtree s = new segtree();
s.build(r);
int n = r.length;
stash[0] = n;
ord[n] = -1;
int front = 1;
int back = 1;
for(int i=0; i<r.length; i++) {
int p = s.find_zero();
while(p==-1) {
s.decr(stash[front]-k+1+n, n-1);
front++;
p = s.find_zero();
}
ord[p] = i;
s.pt_update(p);
if(p<k-1) {
s.decr(0, p);
stash[back] = p;
back++;
} else {
s.decr(p-k+1, p);
}
ptr[p] = ord[stash[front-1]];
}
}
void init(int k, int[] r) {
lexi_smallest(k, r, p_lt, tallest);
for(int i=0; i<r.length; i++) {
r[i] = k-1-r[i];
}
lexi_smallest(k, r, p_rg, shortest);
}
int compare_plants(int x, int y) {
if(x>y) return -compare_plants(y,x);
if(tallest[x]>tallest[y] || p_rg[y]>=shortest[x]) return -1;
if(shortest[x]>shortest[y] || p_lt[y]>=tallest[x]) return 1;
return 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
22948 KB |
Output is correct |
2 |
Correct |
150 ms |
22920 KB |
Output is correct |
3 |
Correct |
129 ms |
22796 KB |
Output is correct |
4 |
Correct |
131 ms |
22988 KB |
Output is correct |
5 |
Correct |
141 ms |
22724 KB |
Output is correct |
6 |
Correct |
427 ms |
38872 KB |
Output is correct |
7 |
Correct |
541 ms |
39364 KB |
Output is correct |
8 |
Correct |
729 ms |
41360 KB |
Output is correct |
9 |
Correct |
816 ms |
40536 KB |
Output is correct |
10 |
Correct |
769 ms |
42104 KB |
Output is correct |
11 |
Correct |
763 ms |
40108 KB |
Output is correct |
12 |
Correct |
792 ms |
40788 KB |
Output is correct |
13 |
Correct |
671 ms |
39108 KB |
Output is correct |
14 |
Correct |
799 ms |
39740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
22604 KB |
Output is correct |
2 |
Correct |
150 ms |
22796 KB |
Output is correct |
3 |
Correct |
283 ms |
22632 KB |
Output is correct |
4 |
Correct |
152 ms |
22780 KB |
Output is correct |
5 |
Correct |
143 ms |
22792 KB |
Output is correct |
6 |
Correct |
211 ms |
24328 KB |
Output is correct |
7 |
Correct |
567 ms |
39840 KB |
Output is correct |
8 |
Correct |
192 ms |
23836 KB |
Output is correct |
9 |
Correct |
234 ms |
24108 KB |
Output is correct |
10 |
Correct |
528 ms |
39572 KB |
Output is correct |
11 |
Correct |
502 ms |
38232 KB |
Output is correct |
12 |
Correct |
589 ms |
39204 KB |
Output is correct |
13 |
Correct |
507 ms |
39512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
135 ms |
22604 KB |
Output is correct |
2 |
Correct |
150 ms |
22796 KB |
Output is correct |
3 |
Correct |
283 ms |
22632 KB |
Output is correct |
4 |
Correct |
152 ms |
22780 KB |
Output is correct |
5 |
Correct |
143 ms |
22792 KB |
Output is correct |
6 |
Correct |
211 ms |
24328 KB |
Output is correct |
7 |
Correct |
567 ms |
39840 KB |
Output is correct |
8 |
Correct |
192 ms |
23836 KB |
Output is correct |
9 |
Correct |
234 ms |
24108 KB |
Output is correct |
10 |
Correct |
528 ms |
39572 KB |
Output is correct |
11 |
Correct |
502 ms |
38232 KB |
Output is correct |
12 |
Correct |
589 ms |
39204 KB |
Output is correct |
13 |
Correct |
507 ms |
39512 KB |
Output is correct |
14 |
Correct |
502 ms |
37924 KB |
Output is correct |
15 |
Correct |
1193 ms |
43476 KB |
Output is correct |
16 |
Correct |
582 ms |
39240 KB |
Output is correct |
17 |
Correct |
1194 ms |
42188 KB |
Output is correct |
18 |
Correct |
907 ms |
39452 KB |
Output is correct |
19 |
Correct |
997 ms |
45472 KB |
Output is correct |
20 |
Correct |
1224 ms |
37704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
139 ms |
22544 KB |
Output is correct |
2 |
Correct |
138 ms |
23056 KB |
Output is correct |
3 |
Correct |
548 ms |
39820 KB |
Output is correct |
4 |
Correct |
861 ms |
39408 KB |
Output is correct |
5 |
Correct |
878 ms |
40836 KB |
Output is correct |
6 |
Correct |
1077 ms |
44508 KB |
Output is correct |
7 |
Correct |
1205 ms |
40308 KB |
Output is correct |
8 |
Correct |
1184 ms |
40844 KB |
Output is correct |
9 |
Correct |
1000 ms |
40216 KB |
Output is correct |
10 |
Correct |
763 ms |
40000 KB |
Output is correct |
11 |
Correct |
771 ms |
38760 KB |
Output is correct |
12 |
Correct |
778 ms |
40156 KB |
Output is correct |
13 |
Correct |
874 ms |
40928 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
126 ms |
22904 KB |
Output is correct |
2 |
Correct |
132 ms |
22948 KB |
Output is correct |
3 |
Correct |
314 ms |
22828 KB |
Output is correct |
4 |
Correct |
133 ms |
22828 KB |
Output is correct |
5 |
Correct |
161 ms |
22756 KB |
Output is correct |
6 |
Correct |
195 ms |
23428 KB |
Output is correct |
7 |
Correct |
282 ms |
30616 KB |
Output is correct |
8 |
Correct |
266 ms |
29220 KB |
Output is correct |
9 |
Correct |
288 ms |
29584 KB |
Output is correct |
10 |
Correct |
281 ms |
28368 KB |
Output is correct |
11 |
Correct |
284 ms |
27364 KB |
Output is correct |
12 |
Correct |
257 ms |
30256 KB |
Output is correct |
13 |
Correct |
255 ms |
27592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
22728 KB |
Output is correct |
2 |
Correct |
130 ms |
22916 KB |
Output is correct |
3 |
Correct |
115 ms |
22604 KB |
Output is correct |
4 |
Correct |
124 ms |
23056 KB |
Output is correct |
5 |
Correct |
177 ms |
23136 KB |
Output is correct |
6 |
Correct |
807 ms |
40312 KB |
Output is correct |
7 |
Correct |
940 ms |
37992 KB |
Output is correct |
8 |
Correct |
1134 ms |
40340 KB |
Output is correct |
9 |
Correct |
1184 ms |
45312 KB |
Output is correct |
10 |
Correct |
774 ms |
37808 KB |
Output is correct |
11 |
Correct |
1093 ms |
42052 KB |
Output is correct |
12 |
Correct |
887 ms |
39804 KB |
Output is correct |
13 |
Correct |
1016 ms |
41228 KB |
Output is correct |
14 |
Correct |
1064 ms |
40216 KB |
Output is correct |
15 |
Correct |
1091 ms |
41472 KB |
Output is correct |
16 |
Correct |
835 ms |
39916 KB |
Output is correct |
17 |
Correct |
878 ms |
40520 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
22948 KB |
Output is correct |
2 |
Correct |
150 ms |
22920 KB |
Output is correct |
3 |
Correct |
129 ms |
22796 KB |
Output is correct |
4 |
Correct |
131 ms |
22988 KB |
Output is correct |
5 |
Correct |
141 ms |
22724 KB |
Output is correct |
6 |
Correct |
427 ms |
38872 KB |
Output is correct |
7 |
Correct |
541 ms |
39364 KB |
Output is correct |
8 |
Correct |
729 ms |
41360 KB |
Output is correct |
9 |
Correct |
816 ms |
40536 KB |
Output is correct |
10 |
Correct |
769 ms |
42104 KB |
Output is correct |
11 |
Correct |
763 ms |
40108 KB |
Output is correct |
12 |
Correct |
792 ms |
40788 KB |
Output is correct |
13 |
Correct |
671 ms |
39108 KB |
Output is correct |
14 |
Correct |
799 ms |
39740 KB |
Output is correct |
15 |
Correct |
135 ms |
22604 KB |
Output is correct |
16 |
Correct |
150 ms |
22796 KB |
Output is correct |
17 |
Correct |
283 ms |
22632 KB |
Output is correct |
18 |
Correct |
152 ms |
22780 KB |
Output is correct |
19 |
Correct |
143 ms |
22792 KB |
Output is correct |
20 |
Correct |
211 ms |
24328 KB |
Output is correct |
21 |
Correct |
567 ms |
39840 KB |
Output is correct |
22 |
Correct |
192 ms |
23836 KB |
Output is correct |
23 |
Correct |
234 ms |
24108 KB |
Output is correct |
24 |
Correct |
528 ms |
39572 KB |
Output is correct |
25 |
Correct |
502 ms |
38232 KB |
Output is correct |
26 |
Correct |
589 ms |
39204 KB |
Output is correct |
27 |
Correct |
507 ms |
39512 KB |
Output is correct |
28 |
Correct |
502 ms |
37924 KB |
Output is correct |
29 |
Correct |
1193 ms |
43476 KB |
Output is correct |
30 |
Correct |
582 ms |
39240 KB |
Output is correct |
31 |
Correct |
1194 ms |
42188 KB |
Output is correct |
32 |
Correct |
907 ms |
39452 KB |
Output is correct |
33 |
Correct |
997 ms |
45472 KB |
Output is correct |
34 |
Correct |
1224 ms |
37704 KB |
Output is correct |
35 |
Correct |
139 ms |
22544 KB |
Output is correct |
36 |
Correct |
138 ms |
23056 KB |
Output is correct |
37 |
Correct |
548 ms |
39820 KB |
Output is correct |
38 |
Correct |
861 ms |
39408 KB |
Output is correct |
39 |
Correct |
878 ms |
40836 KB |
Output is correct |
40 |
Correct |
1077 ms |
44508 KB |
Output is correct |
41 |
Correct |
1205 ms |
40308 KB |
Output is correct |
42 |
Correct |
1184 ms |
40844 KB |
Output is correct |
43 |
Correct |
1000 ms |
40216 KB |
Output is correct |
44 |
Correct |
763 ms |
40000 KB |
Output is correct |
45 |
Correct |
771 ms |
38760 KB |
Output is correct |
46 |
Correct |
778 ms |
40156 KB |
Output is correct |
47 |
Correct |
874 ms |
40928 KB |
Output is correct |
48 |
Correct |
126 ms |
22904 KB |
Output is correct |
49 |
Correct |
132 ms |
22948 KB |
Output is correct |
50 |
Correct |
314 ms |
22828 KB |
Output is correct |
51 |
Correct |
133 ms |
22828 KB |
Output is correct |
52 |
Correct |
161 ms |
22756 KB |
Output is correct |
53 |
Correct |
195 ms |
23428 KB |
Output is correct |
54 |
Correct |
282 ms |
30616 KB |
Output is correct |
55 |
Correct |
266 ms |
29220 KB |
Output is correct |
56 |
Correct |
288 ms |
29584 KB |
Output is correct |
57 |
Correct |
281 ms |
28368 KB |
Output is correct |
58 |
Correct |
284 ms |
27364 KB |
Output is correct |
59 |
Correct |
257 ms |
30256 KB |
Output is correct |
60 |
Correct |
255 ms |
27592 KB |
Output is correct |
61 |
Correct |
531 ms |
40332 KB |
Output is correct |
62 |
Correct |
487 ms |
39152 KB |
Output is correct |
63 |
Correct |
734 ms |
39228 KB |
Output is correct |
64 |
Correct |
845 ms |
40252 KB |
Output is correct |
65 |
Correct |
951 ms |
40632 KB |
Output is correct |
66 |
Correct |
1177 ms |
42292 KB |
Output is correct |
67 |
Correct |
1097 ms |
41104 KB |
Output is correct |
68 |
Correct |
749 ms |
37804 KB |
Output is correct |
69 |
Correct |
1036 ms |
44044 KB |
Output is correct |
70 |
Correct |
878 ms |
39740 KB |
Output is correct |
71 |
Correct |
871 ms |
40428 KB |
Output is correct |
72 |
Correct |
1036 ms |
41700 KB |
Output is correct |
73 |
Correct |
1096 ms |
44480 KB |
Output is correct |
74 |
Correct |
755 ms |
40080 KB |
Output is correct |
75 |
Correct |
848 ms |
40608 KB |
Output is correct |