#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "plants.h"
vector<int> it;
int n;
int k;
pair<int,int> tree[800001];
int lazy[800001];
void build(int no,int l,int r){
if(l==r){
tree[no]={it[l],l};
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
if(tree[no*2+1].a<tree[no*2+2].a){
tree[no]=tree[no*2+1];
}
else{
tree[no]=tree[no*2+2];
}
}
}
void update(int no,int l,int r,int aa,int bb){
tree[no].a+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
if(l>aa or r<bb){
return ;
}
if(aa<=l and r<=bb){
tree[no].a-=1;
if(l<r){
lazy[no*2+1]-=1;
lazy[no*2+2]-=1;
}
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb);
update(no*2+2,mid+1,r,aa,bb);
if(tree[no*2+1].a<tree[no*2+2].a){
tree[no]=tree[no*2+1];
}
else{
tree[no]=tree[no*2+2];
}
}
}
void update2(int no,int l,int r,int i){
tree[no].a+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
if(l==r){
tree[no]={1e9,-1};
}
else{
int mid=(l+r)/2;
if(i<=mid){
update2(no*2+1,l,mid,i);
}
else{
update2(no*2+2,mid+1,r,i);
}
if(tree[no*2+1].a<tree[no*2+2].a){
tree[no]=tree[no*2+1];
}
else{
tree[no]=tree[no*2+2];
}
}
}
int tree2[200001];
void u(int i,int j){
while(i<200001){
tree2[i]+=j;
i+=(i&-i);
}
}
int ss(int i){
int su=0;
while(i>0){
su+=tree2[i];
i-=(i&-i);
}
return su;
}
int ans[200001];
set<int> cur;
bool check(int j){
if(cur.size()==1){
return true;
}
auto jj=cur.find(j);
int dis;
if(jj==cur.begin()){
jj=cur.end();
jj--;
dis=j+n-*jj;
}
else{
jj--;
dis=j-*jj;
}
if(dis>k-1){
return true;
}
return false;
}
void init(int kk,vector<int> r){
n=r.size();
k=kk;
it=r;
build(0,0,n-1);
set<int> cur2;
for(int i=0;i<n;i++){
if(it[i]==0){
cur.insert(i);
update2(0,0,n-1,i);
}
}
for(auto j:cur){
if(check(j)){
cur2.insert(j);
}
}
for(int i=0;i<n;i++){
int ind=-1;
/* cur2.clear();
for(auto j:cur){
if(check(j)){
cur2.insert(j);
}
}*/
ind=*(cur2.begin());
ans[ind]=i;
//int cot=ind;
cur2.erase(ind);
cur.erase(ind);
if(cur.size()){
auto j=cur.upper_bound(ind);
if(j!=cur.end()){
if(check(*j)){
cur2.insert(*j);
}
}
else{
j=cur.begin();
if(check(*j)){
cur2.insert(*j);
}
}
}
//cout<<ind<<endl;
if(ind>=k-1){
update(0,0,n-1,ind-k+1,ind-1);
}
else{
if(ind){
update(0,0,n-1,0,ind-1);
}
int xx=(ind-k+1+n)%n;
update(0,0,n-1,xx,n-1);
}
int cot=ind;
for(int jj=0;jj<k-1;jj++){
cot=(cot-1+n)%n;
it[cot]-=1;
if(it[cot]==0){
cur.insert(cot);
if(cur.size()>1){
auto j=cur.upper_bound(cot);
if(j==cur.end()){
j=cur.begin();
cur2.erase(*j);
if(check(*j)){
cur2.insert(*j);
}
}
else{
cur2.erase(*j);
if(check(*j)){
cur2.insert(*j);
}
}
}
//cout<<tree[0].b<<endl;
//cur.insert(cot);
if(check(cot)){
cur2.insert(tree[0].b);
}
//update2(0,0,n-1,tree[0].b);
}
}
continue;
/*if(tree[0].a<0){
while(true){
continue;
}
}*/
while(tree[0].a==0){
cur.insert(tree[0].b);
if(cur.size()>1){
auto j=cur.upper_bound(tree[0].b);
if(j==cur.end()){
j=cur.begin();
cur2.erase(*j);
if(check(*j)){
cur2.insert(*j);
}
}
else{
cur2.erase(*j);
if(check(*j)){
cur2.insert(*j);
}
}
}
//cout<<tree[0].b<<endl;
if(check(tree[0].b)){
cur2.insert(tree[0].b);
}
update2(0,0,n-1,tree[0].b);
}
}
return;
}
int compare_plants(int x, int y) {
/* x=dis[x];
y=dis[y];*/
if(ans[x]<ans[y]){
return 1;
}
else{
return -1;
}
return 0;
if(y-x<k){
if(it[x]==0){
return 1;
}
else if(it[x]==k-1){
return -1;
}
}
else{
if(it[y]==0){
return -1;
}
else if(it[y]==k-1){
return 1;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
512 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
