#include<vector>
#define vi vector<int>
using namespace std;
#include<queue>
#include <set>
const int siz = 2e5+2;
int ans[siz];
int N,K;
vi R;
int dis(int a, int b){ // oriented
if(b > a)return b-a;
return b-a+K;
}
queue<int> q;
struct node{
int l,r,mid,minir,plus;
node* sl,*sr;
node(int li, int ri){
l = li, r = ri, mid = (l+r)/2,plus=0;
if(l<r){
sl = new node(l,mid);
sr = new node(mid+1,r);
minir = min(sl->minir,sr->minir);
}else{
minir = R[l];
}
}
void push(){
if(l==r)return;
sl->minir+=plus;
sr->minir+=plus;
sl->plus+=plus;
sr->plus+=plus;
plus=0;
}
void update(int a, int b, int p){
push();
if(r < a || l > b)return;
if(a <= l && b >= r){
minir+=p;
plus+=p;
}else{
sl->update(a,b,p);
sr->update(a,b,p);
minir = min(sl->minir,sr->minir);
}
}
int find(){
push();
if(l==r){
if(minir<=0){
update(l,l,1e9-minir);
return l;
}
else return 1e9;
}
if(sl->minir<=0){
return sl->find();
}
else return sr->find();
}
};
set<int> s;
node* seg;
bool check(int i){
auto it = s.find(i);
if(it == s.end())return 0;
auto it2 = it;
it2--;
if(it2 == s.begin())it2 = --s.end();
if(it2 == s.end() || dis(*it2,i)>=K ){
return 1;
}
else{
q.push(i);
return 0;
}
}
void ins(int i){ // he now has r[i]=0
//auto it = s.find(i);
s.insert(i);
//check(i);
}
int mod(int i){
return (i+N)%N;
}
void er(int i){ // i was considered as a maximum
auto it = s.find(i);
if(i>=K-1){
seg->update(i-K+1,i,-1);
}else{
seg->update(0,i,-1);
seg->update(mod(i-K+1),N-1,-1);
}
auto it1 = it, it2 = it;
it2++;
s.erase(i);
if(it2 == s.end())it2 = s.begin();
if(it2!=s.end())check(*it2);
}
void init(int k, std::vector<int> r) {
N = r.size(), K = k, R = r;
seg = new node(0,N-1);
while(true){
int f = seg->find();
if(f==1e9)break;
ins(f);
}
for(int i = 0; i < N; i++)if(r[i]==0){
q.push(i);
check(i);
}
int it = 0;
vi vis(N);
while(!q.empty()){
int i = q.front();
q.pop();
if(vis[i])continue;
if(check(i)==0)continue;
vis[i]=1;
er(i);
ans[i]=it;
it++;
vi vec;
while(true){
int f = seg->find();
if(f==1e9)break;
ins(f);
q.push(f);
}
}
}
int compare_plants(int x, int y) {
if(ans[x]<ans[y])return 1;
return -1;
}
Compilation message
plants.cpp: In function 'void er(int)':
plants.cpp:96:7: warning: variable 'it1' set but not used [-Wunused-but-set-variable]
96 | auto it1 = it, it2 = it;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 4 |
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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
436 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
348 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 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
