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>
#pragma GCC optimize("Ofast")
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct ST{
vector<pair<int,int> > st;
void init(int x){
st.resize(4*x);
}
void pull(int v){
st[v].fs=min(st[2*v+1].fs,st[2*v+2].fs);
}
void upd(int v,int x){
st[v].fs+=x;
st[v].sc+=x;
}
void build(int v,int L,int R,vector<int>& x){
if(L==R){
st[v].fs=x[L];
return;
}
int m=(L+R)/2;
build(2*v+1,L,m,x);
build(2*v+2,m+1,R,x);
pull(v);
}
void pudo(int v){
upd(2*v+1,st[v].sc);
upd(2*v+2,st[v].sc);
st[v].sc=0;
}
void update(int v,int L,int R,int l,int r,int t){
if(L==l && R==r){
upd(v,t);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
update(2*v+1,L,m,l,r,t);
}
else if(l>m){
update(2*v+2,m+1,R,l,r,t);
}
else{
update(2*v+1,L,m,l,m,t);
update(2*v+2,m+1,R,m+1,r,t);
}
pull(v);
}
int finds(int v,int L,int R){
if(L==R){
return L;
}
if(st[v].fs>0){
return -1;
}
int m=(L+R)/2;
pudo(v);
if(st[2*v+1].fs>0){
return finds(2*v+2,m+1,R);
}
else{
return finds(2*v+1,L,m);
}
}
};
int k;
int n;
vector<int> a[2];
void get(vector<int> c,int g){
queue<int> s;
ST st;
int m=2*n;
a[g].resize(m);
st.init(m);
st.build(0,0,m-1,c);
for(int i=0;i<2*n;i++){
int x=st.finds(0,0,m-1);
while(x<0){
auto h=s.front();
s.pop();
st.update(0,0,m-1,h,m-1,-1);
x=st.finds(0,0,m-1);
}
st.update(0,0,m-1,x,x,1e9);
int l=x-k+1;
a[g][x]=i;
if(l<0){
st.update(0,0,m-1,0,x,-1);
s.push(l+m);
}
else{
st.update(0,0,m-1,l,x,-1);
}
}
}
void init(int K, vector<int> r){
k=K;
n=r.size();
vector<int> z(2*n);
for(int i=0;i<n;i++){
z[i]=z[i+n]=r[i];
}
get(z,0);
for(auto& h:z){
h=k-1-h;
}
get(z,1);
}
int compare_plants(int x, int y) {
if(x>y){
return -compare_plants(y,x);
}
if(a[0][x]>a[0][y] || a[1][y]>a[1][x+n]){
return -1;
}
else if(a[1][x]>a[1][y] || a[0][y]>a[0][x+n]){
return 1;
}
return 0;
}
# | 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... |