#include "plants.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) x.size();
using namespace std;
typedef pair<int,int> ii;
struct node{
int s, e, m;
ii val = ii(0,0); int lazy = 0;
node *l, *r;
node(int S, int E){
s = S, e = E, m = (s+e)/2;
if(s == e) val = ii(0, S);
else{
l = new node(s, m);
r = new node(m+1, e);
val = min(l->val, r->val);
}
}
void apply(int L){
val.first += L;
lazy += L;
}
void push(){
if(s == e) return;
l->apply(lazy);
r->apply(lazy);
lazy = 0;
}
void update(int S, int E, int L){
push();
if(s == S && E == e){
apply(L);
return;
}
else if(E <= m) l->update(S, E, L);
else if(S >= m+1) r->update(S, E, L);
else l->update(S, m, L), r->update(m+1, E, L);
val = min(l->val, r->val);
}
ii query(int S, int E){
push();
if(s == S && E == e) return val;
else if(E <= m) return l->query(S, E);
else if(S >= m+1) return r->query(S, E);
else return min(l->query(S, m), r->query(m+1, E));
}
} *root;
int n, K;
int H[200005];
int height;
void assign(int u){
while(true){
int R = u-1, L = u-K+1;
if(L < 0) L += n; if(R < 0) R += n;
ii res;
if(L <= R){
res = root->query(L,R);
}
else{
res = min(root->query(L, n-1), root->query(0,R));
}
if(res.first == 0) assign(res.second);
else break;
}
H[u] = height;
int R = u-1, L = u-K+1;
if(L < 0) L += n; if(R < 0) R += n;
if(L <= R){
root->update(L, R, -1);
}
else{
root->update(L, n-1, -1); root->update(0, R, -1);
}
root->update(u, u, 1e9);
height--;
}
void init(int _K, vector<int> R) {
n = sz(R); K = _K;
root = new node(0, n-1);
for(int i = 0;i < n;i++) root->update(i,i,R[i]);
fill(H,H+n,-1);
height = n-1;
while(height >= 0){
ii res = root->query(0, n-1);
assign(res.second);
}
//for(int i = 0;i < n;i++) cout << H[i] << " ";
return;
}
int compare_plants(int x, int y) {
if(H[x] > H[y]) return 1;
else return -1;
}
Compilation message
plants.cpp: In function 'void assign(int)':
plants.cpp:63:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
63 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:63:21: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
63 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:78:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
78 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
plants.cpp:78:20: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
78 | if(L < 0) L += n; if(R < 0) R += n;
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
4 ms |
620 KB |
Output is correct |
7 |
Correct |
72 ms |
5612 KB |
Output is correct |
8 |
Correct |
2 ms |
492 KB |
Output is correct |
9 |
Correct |
4 ms |
620 KB |
Output is correct |
10 |
Correct |
71 ms |
5584 KB |
Output is correct |
11 |
Correct |
67 ms |
5484 KB |
Output is correct |
12 |
Correct |
68 ms |
5740 KB |
Output is correct |
13 |
Correct |
70 ms |
5612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
364 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
4 ms |
620 KB |
Output is correct |
7 |
Correct |
72 ms |
5612 KB |
Output is correct |
8 |
Correct |
2 ms |
492 KB |
Output is correct |
9 |
Correct |
4 ms |
620 KB |
Output is correct |
10 |
Correct |
71 ms |
5584 KB |
Output is correct |
11 |
Correct |
67 ms |
5484 KB |
Output is correct |
12 |
Correct |
68 ms |
5740 KB |
Output is correct |
13 |
Correct |
70 ms |
5612 KB |
Output is correct |
14 |
Correct |
108 ms |
7532 KB |
Output is correct |
15 |
Correct |
760 ms |
27744 KB |
Output is correct |
16 |
Correct |
107 ms |
7532 KB |
Output is correct |
17 |
Correct |
768 ms |
27712 KB |
Output is correct |
18 |
Correct |
429 ms |
27116 KB |
Output is correct |
19 |
Correct |
434 ms |
27688 KB |
Output is correct |
20 |
Correct |
665 ms |
27664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
68 ms |
5100 KB |
Output is correct |
4 |
Correct |
352 ms |
29932 KB |
Output is correct |
5 |
Correct |
419 ms |
27372 KB |
Output is correct |
6 |
Correct |
640 ms |
27244 KB |
Output is correct |
7 |
Correct |
744 ms |
27372 KB |
Output is correct |
8 |
Correct |
765 ms |
27500 KB |
Output is correct |
9 |
Correct |
371 ms |
27116 KB |
Output is correct |
10 |
Correct |
366 ms |
26860 KB |
Output is correct |
11 |
Correct |
297 ms |
26860 KB |
Output is correct |
12 |
Correct |
349 ms |
26988 KB |
Output is correct |
13 |
Correct |
419 ms |
26988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |