#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
struct AINT {
int n;
vector<ii> V;
vi Lz;
AINT() {}
AINT(int N) : n(N), V(4 * N, ii{0, 0}), Lz(4 * N, 0) {}
void prop(int u, int s, int d) {
if(!Lz[u]) return;
V[u].first += Lz[u];
if(s != d) {
Lz[u << 1] += Lz[u];
Lz[u << 1 | 1] += Lz[u];
}
Lz[u] = 0;
}
void update(int p, ii v, int u, int s, int d) {
prop(u, s, d);
if(d < p || p < s) return;
if(s == d) {
V[u] = v;
return;
}
update(p, v, u << 1, s, (s + d) >> 1);
update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = min(V[u << 1], V[u << 1 | 1]);
}
void update(int p, ii v) { update(p, v, 1, 0, n - 1); }
void update(int l, int r, int v, int u, int s, int d) {
prop(u, s, d);
if(r < s || d < l) return;
if(l <= s && d <= r) {
Lz[u] += v;
prop(u, s, d);
return;
}
update(l, r, v, u << 1, s, (s + d) >> 1);
update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
V[u] = min(V[u << 1], V[u << 1 | 1]);
}
void update(int l, int r, int v) { update(l, r, v, 1, 0, n - 1); }
ii query() {
return V[1];
}
ii query(int l, int r, int u, int s, int d) {
int mij = (s + d) >> 1;
if(l <= s && d <= r) return V[u];
if(r <= mij) return query(l, r, u << 1, s, mij);
if(l > mij) return query(l, r, u << 1 | 1, mij + 1, d);
return min(query(l, r, u << 1, s, mij), query(l, r, u << 1 | 1, mij + 1, d));
}
ii query(int l, int r) {
if(l < 0 && r < 0) {
l += n;
r += n;
}
if(r >= n && l >= n) {
l -= n;
r -= n;
}
if(l >= 0 && r < n) return query(l, r, 1, 0, n - 1);
if(l < 0 && r >= n) return query(0, n - 1, 1, 0, n - 1);
if(l < 0) {
return min(query(0, r, 1, 0, n - 1), query(l + n, n - 1, 1, 0, n - 1));
}
if(r >= n) {
return min(query(l, n - 1, 1, 0, n - 1), query(0, r - n, 1, 0, n - 1));
}
}
};
const int INF = 1e9;
vi Perm;
vi stanga, dreapta;
int n, k;
void init(int k, vi r) {
::k = k;
n = int(r.size());
vi active(n, 1);
AINT Sol(n);
for(int i = 0; i < n; ++i) {
Sol.update(i, {r[i], i});
}
set<int> Zero, ZeroActiv;
while(!Sol.query().first) {
int p = Sol.query().second;
Zero.insert(p);
Sol.update(p, {INF, p});
}
auto get_urm = [&](int p) {
auto it = Zero.upper_bound(p);
if(it == Zero.end()) return *Zero.begin();
return *it;
};
auto get_prev = [&](int p) {
auto it = Zero.lower_bound(p);
if(it == Zero.begin()) return *Zero.rbegin();
--it;
return *it;
};
auto dist = [&](int a, int b) {
//!!! distanta directionata
if(a < b) return b - a;
return b + n - a - 1;
};
for(auto it : Zero) {
int u = get_prev(it);
if(it == u || dist(it, u) >= k)
ZeroActiv.insert(it);
}
auto erase = [&](int u) {
int urm = get_urm(u);
ZeroActiv.erase(u);
Zero.erase(u);
if(urm != u) {
int nou_pr = get_prev(urm);
if(nou_pr == urm || dist(nou_pr, urm) >= k) {
ZeroActiv.insert(urm);
}
}
};
auto insert = [&](int u) {
Zero.insert(u);
int urm = get_urm(u);
if(urm == u) {
ZeroActiv.insert(u);
return;
}
if(dist(u, urm) < k) {
ZeroActiv.erase(urm);
}
int ant = get_prev(u);
if(dist(ant, u) >= k)
ZeroActiv.insert(u);
};
Perm.resize(n);
vi ord;
for(int nr = 0; nr < n; ++nr) {
int u = *ZeroActiv.begin();
erase(u);
int l = u - k + 1;
if(l < 0) {
Sol.update(0, u, -1);
l = n + l;
Sol.update(l, n - 1, -1);
} else {
Sol.update(l, u, -1);
}
while(Sol.query().first == 0) {
int p = Sol.query().second; /// a fost popit
insert(p);
Sol.update(p, ii{INF, p});
}
Perm[u] = n - nr - 1;
ord.push_back(u);
}
AINT A2(n);
for(int i = 0; i < n; ++i)
A2.update(i, {-Perm[i], i});
stanga.resize(2 * n, -1);
dreapta.resize(2 * n, -1);
for(auto it : ord) {
A2.update(it, it, INF);// dezactivam
auto [v1, p1] = A2.query(it - k + 1, it - 1);
if(v1 <= 0) {
if(p1 > n) {
p1 -= n;
}
stanga[it] = p1;
stanga[it + n] = p1 + n;
}
auto [v2, p2] = A2.query(it + 1, it + k - 1);
if(v2 <= 0) {
if(p2 < it) p2 += n;
dreapta[it] = p2;
dreapta[it + n] = p2 + n;
}
}
}
bool comparable_dr(int x, int y) {
if(Perm[x] < Perm[y]) {
swap(x, y);
}
if(y < x)
y += n;
while(x < y) {
if(dreapta[x] == -1) {
return false;
}
if(dreapta[x] < y) {
x = dreapta[x];
if(Perm[x % n] < Perm[y % n]) return false;
continue;
}
return true;
}
return true;
}
bool comparable_st(int x, int y) {
if(Perm[x] < Perm[y]) {
swap(x, y);
}
if(y > x)
x += n;
//acum y < x
while(x > y) {
if(stanga[x] < 0) {
return false;
}
if(stanga[x] > y) {
x = stanga[x];
if(Perm[x % n] < Perm[y % n]) return false;
continue;
}
return true;
}
return true;
}
bool comparable(int x, int y) {
return comparable_st(x, y) || comparable_dr(x, y);
}
int compare_plants(int x, int y) {
if(!comparable(x, y)) return 0;
if(Perm[x] < Perm[y]) return -1;
return 1;
}
Compilation message
plants.cpp: In member function 'ii AINT::query(int, int)':
plants.cpp:86:5: warning: control reaches end of non-void function [-Wreturn-type]
86 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
237 ms |
4864 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
432 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
