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>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;
int n, k;
vector<int> vc1, vc2;
struct LAZY_SEG{
LL tree[1600010], lazy[1600010];
void prop(int point, int s, int e){
if(s==e)tree[point]+=lazy[point];
else{
lazy[point*2]+=lazy[point];
lazy[point*2+1]+=lazy[point];
}
lazy[point]=0;
}
void eat(int point){
tree[point]=min(tree[point*2]+lazy[point*2], tree[point*2+1]+lazy[point*2+1]);
}
void init(){
memset(tree, 0, sizeof tree);
memset(lazy, 0, sizeof lazy);
}
void alter(int point, int s, int e, int a, int b, LL val){
if(e<a||s>b)return;
if(a<=s&&e<=b){
lazy[point]+=val;
return;
}
prop(point, s, e);
alter(point*2, s, (s+e)/2, a, b, val);
alter(point*2+1, (s+e)/2+1, e, a, b, val);
eat(point);
}
int argmin(int point, int s, int e){
if(tree[point]+lazy[point]>0)return -1;
if(s==e)return s;
prop(point, s, e);
int ret=argmin(point*2, s, (s+e)/2);
if(ret<0)ret=argmin(point*2+1, (s+e)/2+1, e);
eat(point);
return ret;
}
}seg;
int stk[400010], re;
vector<int> calc(vector<int> vc){
vector<int> ret;
ret.resize(vc.size());
re=0;
seg.init();
for(int i=0; i<2*n; i++){
seg.alter(1, 0, 2*n-1, i, i, (LL)vc[i]);
}
for(int i=1; i<=2*n; i++){
int x;
while(1){
x=seg.argmin(1, 0, 2*n-1);
if(x>=0)break;
seg.alter(1, 0, 2*n-1, stk[re], 2*n-1, -1);
re--;
}
ret[x]=i;
seg.alter(1, 0, 2*n-1, x, x, LLINF);
seg.alter(1, 0, 2*n-1, x-k+1, x-1, -1);
if(x-k+1<0)stk[++re]=2*n+x-k;
}
return ret;
}
void init(int _k, vector<int> r) {
n=r.size(); k=_k;
for(int i=0; i<n; i++)r.eb(r[i]);
vc1=calc(r);
for(int i=0; i<2*n; i++)r[i]=k-1-r[i];
vc2=calc(r);
}
int compare_plants(int x, int y){
if(x>y)return -compare_plants(y, x);
if(vc1[x]>vc1[y]||vc2[x+n]<vc2[y])return -1;
if(vc2[x]>vc2[y]||vc1[x+n]<vc1[y])return 1;
return 0;
}
/*
4 3 2
0 1 1 2
0 2
1 2
*/
# | 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... |