#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;
int id[MAX];
struct ST{
pii tree[4 * MAX];
int lazy[4 * MAX];
pii comb(pii a, pii b){
if(a.first < b.first) return a;
return b;
}
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] = comb(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 comb(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;
void update(int l, int r, int val){
if(r < l){
st.update(1, 1, n, l, n, val);
st.update(1, 1, n, 1, r, val);
}
else st.update(1, 1, n, l, r, val);
}
void add(int i){
if(!s.size()){
s.insert(i);
dif.insert({n, i});
return;
}
auto itr = s.lower_bound(i);
if(itr == s.begin()) dif.insert({n - (*s.rbegin() - i), i});
else dif.insert({i - *prev(itr), i});
if(itr == s.end()){
dif.erase({n - (*s.rbegin() - *s.begin()), *s.begin()});
dif.insert({n - (i - *s.begin()), *s.begin()});
}
else{
dif.erase({*itr - *prev(itr), *itr});
dif.insert({*itr - i, *itr});
}
s.insert(i);
}
void rem(int i){
s.erase(i);
if(!s.size()) return;
auto itr = s.lower_bound(i);
if(itr == s.begin()) dif.erase({n - (*s.rbegin() - i), i});
else dif.erase({i - *prev(itr), i});
if(itr == s.end()){
dif.erase({n - (i - *s.begin()), *s.begin()});
dif.insert({n - (*s.rbegin() - *s.begin()), *s.begin()});
}
else{
dif.erase({*itr - i, *itr});
dif.insert({*itr - *prev(itr), *itr});
}
}
void init(int k, vector<int> r) {
n = r.size();
r.insert(r.begin(), 0);
for(int i = 1; i <= n; i++){
st.update(1, 1, n, i, i, r[i]);
if(!r[i]) s.insert(i);
}
int pr = 0;
for(int a : s){
if(pr) dif.insert({a - pr, a});
pr = a;
}
if(s.size() > 1) dif.insert({n - (*s.rbegin() - *s.begin()), *s.begin()});
int t = n;
while(s.size()){
int f = dif.begin()->second;
rem(f);
if(dif.begin()->first < k) continue;
int l = f - k + 1;
if(l <= 0) l += n;
id[f] = t--;
update(l, f - 1, -1);
while(st.ask(1, 1, n, 1, n).first == 0){
int a = st.ask(1, 1, n, 1, n).second;
update(a, a, oo);
add(a);
}
}
}
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 |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Execution timed out |
4085 ms |
10844 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6488 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
