#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct T{
int mn,pos;
}st[800001];
T operator +(T a, T b){
return (a.mn>b.mn?b:a);
}
int n,k,lazy[800001],p[200001];
vector <int> a;
void down(int node, int l, int r){
if (!lazy[node]||l==r)
return;
st[node<<1].mn+=lazy[node];
st[node<<1|1].mn+=lazy[node];
lazy[node<<1]+=lazy[node];
lazy[node<<1|1]+=lazy[node];
lazy[node]=0;
}
void build(int node, int l, int r){
if (l==r){
st[node]={a[l],l};
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v, int val){
if (l>v||r<u||u>v)
return;
if (l>=u&&r<=v){
st[node].mn+=val;
lazy[node]+=val;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
update(node<<1,l,mid,u,v,val);
update(node<<1|1,mid+1,r,u,v,val);
st[node]=st[node<<1]+st[node<<1|1];
}
T get(int node, int l, int r, int u, int v){
if (l>v||r<u||u>v)
return {INF,0};
if (l>=u&&r<=v)
return st[node];
down(node,l,r);
int mid=(l+r)>>1;
return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
int calc(int j){
T t={INF,0};
if (j<k)
t=get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1);
else
t=get(1,0,n-1,j-k+1,j-1);
if (t.mn)
return -1;
return t.pos;
}
T get(int l, int r){
l=(l%n+n)%n;
r=(r%n+n)%n;
if (l<=r)
return get(1,0,n-1,l,r);
else{
T t=get(1,0,n-1,l,n-1);
if (!t.mn)
return t;
else
return get(1,0,n-1,0,r);
}
}
void init(int K, vector <int> r){
k=K;
a=r;
n=a.size();
build(1,0,n-1);
int j=st[1].pos;
while (true){
int tmp=calc(j);
if (tmp==-1)
break;
j=tmp;
}
p[j]=n-1;
if (j<k){
update(1,0,n-1,0,j-1,-1);
update(1,0,n-1,n+j-k+1,n-1,-1);
}
else
update(1,0,n-1,j-k+1,j-1,-1);
update(1,0,n-1,j,j,INF);
for (int i=n-2;i;i--){
j=st[1].pos;
assert(!get(1,0,n-1,j,j).mn);
while (true){
int tmp=calc(j);
if (tmp==-1)
break;
j=tmp;
}
p[j]=i;
if (j<k){
update(1,0,n-1,0,j-1,-1);
update(1,0,n-1,n+j-k+1,n-1,-1);
}
else
update(1,0,n-1,j-k+1,j-1,-1);
update(1,0,n-1,j,j,INF);
}
for (int i=0;i<n;i++)
cout << p[i] << ' ';
cout << '\n';
}
int compare_plants(int x, int y){
return (p[x]>p[y]?1:(p[x]<p[y]?-1:0));
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
