#pragma GCC optimize("Ofast")
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int SZ = 1<<18;
const int inf = 1e9;
int R[MAXN];
int n;
typedef pair<int, int> pii;
pii operator+(pii a, pii b) {
return pii(a.first+b.first, a.second+b.second);
}
class stree {
public:
int mn[2*SZ];
int lz[2*SZ];
stree() {}
void reset(bool tp) {
memset(lz, 0, sizeof(int)*2*SZ);
for (int i = SZ; i < 2*SZ; i++) {
mn[i] = (tp && i < SZ+n) ? R[i-SZ] : inf;
}
for (int i = SZ-1; i > 0; i--) mn[i] = min(mn[2*i], mn[2*i+1]);
}
void activate(int p, int cur = 1, int lp = 0, int rp = SZ-1) {
if (lp > p || rp < p) return;
if (lp == rp) {
mn[cur] = lz[cur];
return;
}
int md = (lp+rp)/2;
activate(p, 2*cur, lp, md);
activate(p, 2*cur+1, md+1, rp);
mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
}
void set_lz(int cur, int p) {
lz[cur] += p;
mn[cur] += p;
}
int find(int cur = 1, int lp = 0, int rp = SZ-1, int ulz = 0) { // finds a position that is 0
if (mn[cur]+ulz > 0) return -1;
if (lp == rp) {
mn[cur] = inf;
return lp;
}
ulz += lz[cur];
int md = (lp+rp)/2;
int lq = find(2*cur, lp, md, ulz);
if (lq >= 0) {
mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
return lq;
}
int v = find(2*cur+1, md+1, rp, ulz);
assert(v >= 0);
mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
return v;
}
void upd(int lv, int rv, int v, int cur = 1, int lp = 0, int rp = SZ-1) {
if (lp > rv || rp < lv) return;
if (lp >= lv && rp <= rv) {
set_lz(cur, v);
return;
}
int md = (lp+rp)/2;
upd(lv, rv, v, 2*cur, lp, md);
upd(lv, rv, v, 2*cur+1, md+1, rp);
mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
}
void del(int p, int cur = 1, int lp = 0, int rp = SZ-1) { // can be absorbed into find
if (lp > p || rp < p) return;
if (lp == rp) {
mn[cur] = inf;
return;
}
int md = (lp+rp)/2;
del(p, 2*cur, lp, md); del(p, 2*cur+1, md+1, rp);
mn[cur] = min(mn[2*cur], mn[2*cur+1])+lz[cur];
}
int rt_zero(int lv, int cur = 1, int lp = 0, int rp = SZ-1, int ulz = 0) {
if (rp < lv || mn[cur]+ulz > 0) return n;
if (lp == rp) {
return lp;
}
ulz += lz[cur];
int md = (lp+rp)/2;
int lq = rt_zero(lv, 2*cur, lp, md, ulz);
if (lq < n) return lq;
return rt_zero(lv, 2*cur+1, md+1, rp, ulz);
}
};
stree *tree[2];
int k;
int before[MAXN]; // 0 => 1, 1 => 0, 2 => -1
// if strict, we don't allow x. Otherwise, we optimize for x
void make_strict() { // could x be taller than y
tree[0]->reset(0);
tree[1]->reset(1);
for (int i = 0; i < n; i++) {
int f1;
while ((f1 = tree[1]->find()) >= 0) {
tree[0]->activate(f1);
tree[0]->upd(f1+1, min(n-1, f1+k-1), 1);
if (f1+k-1 >= n) tree[0]->upd(0, f1+k-1-n, 1);
}
int v = tree[0]->find();
if (v == -1) return;
if (v == 0) continue;
before[v]++;
tree[0]->upd(v+1, min(n-1, v+k-1), -1);
tree[0]->upd(0, v+k-1-n, -1);
tree[1]->upd(max(0, v-k+1), v-1, -1);
if (v-k+1 < 0) tree[1]->upd(n+v-k+1, n-1, -1);
}
assert(false);
}
void target(int cur = 0) { // we are trying to activate cur.
// because it is possible, we will never have a cycle
before[cur]++;
while (1) {
int f1;
while ((f1 = tree[1]->rt_zero(max(0, cur-k+1))) < cur) target(f1);
if (cur-k+1 < 0) while ((f1 = tree[1]->rt_zero(n+cur-k+1)) < n) target(f1);
int u = tree[1]->rt_zero(cur);
if (u == n) u = tree[1]->rt_zero(0);
if (u == cur) {
tree[1]->upd(max(0, cur-k+1), cur-1, -1);
if (cur-k+1 < 0) tree[1]->upd(n+cur-k+1, n-1, -1);
tree[1]->del(cur);
return;
}
else target(u);
}
assert(false);
}
void init(int K, vector<int> r) {
k = K;
n = r.size();
assert(n <= 300);
for (int i = 0; i < n; i++) {
R[i] = r[i];
}
tree[0] = new stree(); // 0s to the left
tree[1] = new stree(); // rval
make_strict();
tree[0]->reset(0);
tree[1]->reset(1);
}
int compare_plants(int x, int y) {
return 1-before[y];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8496 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8496 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
8532 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 3 |
Runtime error |
12 ms |
17020 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
8532 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
