#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ll long long
#define oo 1e9
const int MAX = 2e5 + 5;
struct ST{
pii tree[4 * MAX];
int lazy[4 * MAX];
void relax(int node, int l, int r){
tree[node].first += lazy[node];
if(l != r){
lazy[2 * node] += lazy[node];
lazy[2 * node + 1] += lazy[node];
}
lazy[node] = 0;
}
void update(int node, int l, int r, int ul, int ur, int val){
relax(node, l, r);
if(ur < l || r < ul) return;
if(ul <= l && r <= ur){
lazy[node] += val;
relax(node, l, r);
return;
}
int mid = (l + r) / 2;
update(2 * node, l, mid, ul, ur, val);
update(2 * node + 1, mid + 1, r, ul, ur, val);
tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}
pii ask(int node, int l, int r, int ql, int qr){
if(qr < l || r < ql) return {oo, 0};
relax(node, l, r);
if(ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
return min(ask(2 * node, l, mid, ql, qr), ask(2 * node + 1, mid + 1, r, ql, qr));
}
};
int n;
ST st;
set<int> s;
set<pii> dif;
int id[MAX];
void update(int l, int r, int val){
if(r < l){
st.update(1, 0, n - 1, l, n - 1, val);
st.update(1, 0, n - 1, 1, r, val);
}
else st.update(1, 0, n - 1, l, r, val);
}
void add(int i){
if(!s.size()){
s.insert(i);
dif.insert({0, i});
return;
}
s.insert(i);
auto itr = s.find(i);
auto prv = itr, nxt = itr;
if(itr == s.begin()) prv = --s.end();
else prv = prev(itr);
if(itr == prev(s.end())) nxt = s.begin();
else nxt = next(itr);
dif.erase({(*nxt - *prv + n) % n, *nxt});
dif.insert({(*nxt - *itr + n) % n, *nxt});
dif.insert({(*itr - *prv + n) % n, *itr});
}
void rem(int i){
if(s.size() == 1){
s.erase(i);
return;
}
auto itr = s.find(i);
auto prv = itr, nxt = itr;
if(itr == s.begin()) prv = --s.end();
else prv = prev(itr);
if(itr == prev(s.end())) nxt = s.begin();
else nxt = next(itr);
dif.insert({(*nxt - *prv + n) % n, *nxt});
dif.erase({(*nxt - *itr + n) % n, *nxt});
dif.erase({(*itr - *prv + n) % n, *itr});
s.erase(i);
}
void init(int k, vector<int> r) {
n = r.size();
for(int i = 0; i < n; i++){
if(!r[i]){
s.insert(i);
st.update(1, 0, n - 1, i, i, oo);
}
else st.update(1, 0, n - 1, i, i, r[i]);
}
for(auto itr = s.begin(); itr != s.end(); itr++){
dif.insert({(*itr - ((itr != s.begin())? *prev(itr) : *s.rbegin()) + n) % n, *itr});
}
int t = n;
while(s.size()){
int f = dif.rbegin()->second;
cout << f << ' ';
if(dif.rbegin()->first < k && dif.rbegin()->first){
rem(f);
continue;
}
rem(f);
int l = f - k + 1;
if(l <= 0) l += n;
id[f] = t--;
update(l, f - 1, -1);
while(st.ask(1, 0, n - 1, 0, n - 1).first == 0){
int a = st.ask(1, 0, n - 1, 0, n - 1).second;
update(a, a, oo);
add(a);
}
}
// for(int i = 0; i < n; i++) cout << id[i] << ' ';
// cout << '\n';
}
int compare_plants(int x, int y) {
x++, y++;
if(id[x] > id[y]) return 1;
else return -1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8792 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
8536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
