This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end();
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<","<<#y<<" = "<<"("<<x<<"-"<<y<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
vector<int> arr,bigger;
vector<int> seg;
vector<int> laz;
vector<int> pou;
void join(int par, int x, int y){
if(seg[x]<seg[y]){
seg[par] = seg[x];
pou[par] = pou[x];
}
else{
seg[par] = seg[y];
pou[par] = pou[y];
}
}
void push(int par, int x, int y){
seg[x] += laz[par];
laz[x] += laz[par];
seg[y] += laz[par];
laz[y] += laz[par];
laz[par] = 0;
}
void build(int s, int e, int idx){
if(s==e){
seg[idx] = 1e9;
pou[idx] = s;
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
join(idx,idx*2,idx*2+1);
}
void update(int s, int e, int idx, int qs, int qe, int x){
if(qs<=s && e<=qe){
seg[idx] += x;
laz[idx] += x;
return;
}
if(s>qe || e<qs)return;
int mid = (s+e)/2;
push(idx,idx*2,idx*2+1);
update(s,mid,idx*2,qs,qe,x);
update(mid+1,e,idx*2+1,qs,qe,x);
join(idx,idx*2,idx*2+1);
//p2(s,e)
//p2(seg[idx],pou[idx])
}
void init(int k, vector<int> r) {
int n = r.size();
arr.assign(n,0);
bigger.assign(n,0);
seg.assign((n+5)*4,0);
laz.assign((n+5)*4,0);
pou.assign((n+5)*4,0);
int i,j;
build(0,n-1,1);
for(i=0;i<n;i++){
if(r[i]==0){
p(i)
p2(i+k-1,n)
if(i+1<n){
update(0,n-1,1,i+1,min(n-1,i+k-1),1);
}
if(i+k-1>=n){
p((i+k-1)%n)
update(0,n-1,1,0,(i+k-1)%n,1);
}
update(0,n-1,1,i,i,-1e9);
}
}
int curr = n;
for(int t=0;t<n;t++){
int x = pou[1];
//p2(pou[1],seg[1])
arr[x] = curr--;
update(0,n-1,1,x,x,1e9);
//pv(arr)
//for(auto xx : s)
// cout<<xx.pos<<" ";
//cout<<endl;
//pv(bigger)
//pv(r)
//cout<<endl;
if(x+1<n){
update(0,n-1,1,x+1,min(n-1,x+k-1),-1);
}
if(x+k-1>=n){
update(0,n-1,1,0,(x+k-1)%n,-1);
}
for(j=1;j<k;j++){
//cout<<j<<" "<<k<<endl;
int idx = x-j;
if(idx<0)idx+=n;
if(r[idx]>0){
r[idx]--;
if(r[idx]==0){
if(idx+1<n){
update(0,n-1,1,idx+1,min(n-1,idx+k-1),1);
}
if(idx+k-1>=n){
update(0,n-1,1,0,(idx+k-1)%n,1);
}
update(0,n-1,1,idx,idx,-1e9);
}
}
}
//pv(bigger)
//pv(zer)
//pv(r)
}
pv(arr)
}
int compare_plants(int x, int y) {
if(arr[x]>arr[y])return 1;
return -1;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |