//#include "plants.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define S second
#define F first
using namespace std;
const int N=4000006, INF=1e9+7;
int k, n, t[N], dist[N], tt[N], ans[N], Ans, u, o, f[N], ff[N];
set <int> s;
set <pair<int, int> > q;
pair <int, int> p[N];
vector <int> rr;
queue <int> Q;
void build(int l, int r, int x){
if(l==r){t[x]=rr[l-1]; p[x]=make_pair(l, l); return;}
int mid=l+r>>1;
build(l, mid, x<<1);
build(mid+1, r, x<<1|1);
t[x]=max(t[x<<1], t[x<<1|1]);
if(t[x]==t[x<<1])p[x].F=p[x<<1].F;
else p[x].F=p[x<<1|1].F;
if(t[x]==t[x<<1|1])p[x].S=p[x<<1|1].S;
else p[x].S=p[x<<1].S;
}
void push(int x){
t[x]+=tt[x];
tt[x<<1]+=tt[x];
tt[x<<1|1]+=tt[x];
tt[x]=0;
}
void upd(int l, int r, int d, int L, int R, int x){
if(L>r||R<l)return;
if(L==l && R==r){ tt[x]+=d; return; }
push(x);
int mid=L+R>>1;
upd(l, min(mid, r), d, L, mid, x<<1);
upd(max(l, mid+1), r, d, mid+1, R, x<<1|1);
push(x<<1);
push(x<<1|1);
t[x]=max(t[x<<1], t[x<<1|1]);
if(t[x]==t[x<<1])p[x].F=p[x<<1].F;
else p[x].F=p[x<<1|1].F;
if(t[x]==t[x<<1|1])p[x].S=p[x<<1|1].S;
else p[x].S=p[x<<1].S;
}
pair<int, int> ffm(int l, int r, int L, int R, int x){
if(l>r)return make_pair(-1, -1);
if(L==R)return make_pair(L, t[x]+tt[x]);
int mid=L+R>>1;
push(x);
push(x<<1);
push(x<<1|1);
if(t[x<<1]==t[x]&&p[x<<1].S>=l)return ffm(l, min(mid, r), L, mid, x<<1);
else return ffm(max(l, mid+1), r, mid+1, R, x<<1|1);
}
int prev(int x){
set<int>::iterator it=s.lower_bound(x);
if(it==s.begin())it=s.end();
it--;
return *it;
}
int next(int x){
set<int>::iterator it=s.lower_bound(x);
if(it==s.end())it=s.begin();
return *it;
}
void fm(int l, int r){
pair<int, int> pp=ffm(l, r, 1, n, 1);
int x=pp.F;
if(pp.S!=k)return;
if(!s.size()){
s.insert(x);
q.insert(make_pair(-n, x));
dist[x]=n;
fm(x+1, r);
return;
}
int pr=prev(x);
int nx=next(x);
s.insert(x);
pair<int, int> p=make_pair(-dist[nx], nx);
q.erase(p);
dist[nx]=(nx+n-x)%n;
q.insert(make_pair(-dist[nx], nx));
dist[x]=(x+n-pr)%n;
q.insert(make_pair(-dist[x], x));
fm(x+1, r);
}
void upd(int x){
upd(x, x, -INF, 1, n, 1);
int l=x-k, r=x-1;
l+=(l<1)*n;
r+=(r<1)*n;
if(l<=r){
upd(l, r, 1, 1, n, 1);
fm(l, r);
}
else{
upd(1, r, 1, 1, n, 1);
upd(l, n, 1, 1, n, 1);
fm(1, r);
fm(l, n);
}
}
void init(int kk, vector<int> rrr){
k=kk-1;
n=rrr.size();
rr=rrr;
build(1, n, 1);
fm(1, n);
while(q.size()){
Ans++;
while(q.size()>0 && -(*q.begin()).F>k){
Q.push((*q.begin()).S);
s.erase((*q.begin()).S);
q.erase(q.begin());
}
while(!Q.empty()){
int x=Q.front();
if(s.size()>0){
int nx=next(x);
int pr=prev(x);
pair<int, int> p=make_pair(-dist[nx], nx);
q.erase(p);
dist[nx]=(nx+n-pr)%n;
if(dist[nx]==0)dist[nx]=n;
q.insert(make_pair(-dist[nx], nx));
}
ans[x]=Ans;
Q.pop();
upd(x);
}
}
f[1]=ff[1]=1;
q.insert({-ans[1], 1});
o=2;
while(q.size() && o<=n){
int u=-(*q.begin()).F;
if(ans[o]<u){
f[o]=1;
q.insert({-ans[o], o});
}
if(o>k&&f[o-k]){
q.erase({-ans[o-k], o-k});
}
o++;
}
q.clear();
q.insert({ans[1], 1});
o=2;
while(q.size() && o<=n){
int u=(*q.begin()).F;
if(ans[o]>u){
ff[o]=1;
q.insert({ans[o], o});
}
if(o>k&&ff[o-k]){
q.erase({ans[o-k], o-k});
}
o++;
}
q.clear();
q.insert({-ans[1], 1});
o=n;
while(q.size()){
int u=-(*q.begin()).F;
if(ans[o]<u){
f[o]=1;
q.insert({-ans[o], o});
}
int h=o+k;
if(h==n+1)h=1;
if(o+k<n+2&&f[h]){
q.erase({-ans[h], h});
}
o--;
}
q.clear();
q.insert({ans[1], 1});
o=n;
while(q.size()){
int u=(*q.begin()).F;
if(ans[o]>u){
ff[o]=1;
q.insert({ans[o], o});
}
int h=o+k;
if(h==n+1)h=1;
if(o+k<n+2&&ff[h]){
q.erase({ans[h], h});
}
o--;
}
}
int compare_plants(int x, int y) {
return f[y+1]-ff[y+1];
}
Compilation message
plants.cpp: In function 'void build(int, int, int)':
plants.cpp:19:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int mid=l+r>>1;
| ~^~
plants.cpp: In function 'void upd(int, int, int, int, int, int)':
plants.cpp:40:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid=L+R>>1;
| ~^~
plants.cpp: In function 'std::pair<int, int> ffm(int, int, int, int, int)':
plants.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid=L+R>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
0 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
512 KB |
Output is correct |
| 6 |
Correct |
958 ms |
17436 KB |
Output is correct |
| 7 |
Correct |
925 ms |
18168 KB |
Output is correct |
| 8 |
Runtime error |
996 ms |
38264 KB |
Execution killed with signal 11 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
