#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+N;
}
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){
return l;
}
else return 1e9;
}
if(sl->minir<=0){
return sl->find();
}
else if(sr->minir <=0)return sr->find();
else return 1e9;
}
};
set<int> s;
node* seg;
bool check(int i){
for(auto j : s)if(dis(j,i)<K)return 0;
q.push(i);
return 1;
auto it = s.find(i);
if(it == s.end())return 0;
auto it2 = it;
int j;
if(it2!=s.begin())j = *(--it2);
else j = *(s.rbegin());
if(*it2 == i){
q.push(i);
return 1;
}
if(dis(*it2,i)>=K ){
q.push(i);
return 1;
}
else{
return 0;
}
}
void ins(int i){ // he now has r[i]=0
//auto it = s.find(i);
s.insert(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();
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();
seg->update(f,f,1e9);
if(f==1e9)break;
ins(f);
}
for(int i = 0; i < N; i++)if(r[i]==0){
check(i);
}
int ito = 1;
vi vis(N);
while(ito<=N){
int i = q.front();
//for(int j : s)if(check(j))i=j;
q.pop();
if(vis[i])continue;
if(check(i)==0)continue;
vis[i]=1;
er(i);
ans[i]=ito;
ito++;
vi vec;
while(true){
int f = seg->find();
seg->update(f,f,1e9);
if(f==1e9)break;
ins(f);
}
}
/*for(int i = 0; i < N; i++){
if(ans[i]==0){
for(int j = 0; j < 2e9; j++){
ans[i] = (ans[i]+1)%N;
}
}
}*/
int i =5;
return;
}
int compare_plants(int x, int y) {
if(ans[x]<ans[y])return 1;
return -1;
}
Compilation message
plants.cpp: In function 'bool check(int)':
plants.cpp:74:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
74 | int j;
| ^
plants.cpp: In function 'void er(int)':
plants.cpp:104:7: warning: variable 'it1' set but not used [-Wunused-but-set-variable]
104 | auto it1 = it, it2 = it;
| ^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:151:6: warning: unused variable 'i' [-Wunused-variable]
151 | int i =5;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
344 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
