#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];
}
};
const int INF = 1e9;
vi Perm;
void init(int k, vi r) {
int 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);
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;
}
for(auto it : Perm)
cout << it << " ";
cout << "\n";
}
int compare_plants(int x, int y) {
if(Perm[x] < Perm[y]) return -1;
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
