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 <bits/stdc++.h>
#include "plants.h"
using namespace std;
struct node{
int val,lazy;
};
int n,t,k,cnt,val[200001];
vector<node> segment;
void push(int curr){
for(int i = 2*curr ; i <= 2*curr+1 ; i += 1){
segment[i].lazy += segment[curr].lazy , segment[i].val += segment[curr].lazy;
}
segment[curr].lazy = 0;
}
void pull(int curr){
segment[curr].val = min(segment[2*curr].val,segment[2*curr+1].val);
}
void upd(int a , int b , int v , int curr , int l , int r){
if(b < l || a > r){
return ;
}
if(a <= l && b >= r){
segment[curr].val = v , segment[curr].lazy = 0;
return ;
}
int mid = (l+r)/2;
push(curr);
upd(a,b,v,2*curr,l,mid),upd(a,b,v,2*curr+1,mid+1,r);
pull(curr);
}
void rupd(int a , int b , int curr , int l , int r){
if(b < l || a > r){
return ;
}
if(a <= l && b >= r){
segment[curr].lazy -= 1 , segment[curr].val -= 1;
return ;
}
int mid = (l+r)/2;
push(curr);
rupd(a,b,2*curr,l,mid),rupd(a,b,2*curr+1,mid+1,r);
pull(curr);
}
void u(int pos){
val[pos] = cnt++;
upd(pos,pos,1000000000,1,1,t);
if(pos > 1){
if(pos >= k){
rupd(pos-k+1,pos-1,1,1,t);
}else{
int num = k-pos-1;
rupd(1,pos-1,1,1,t),rupd(n-num,n,1,1,t);
}
}else{
rupd(n-k+2,n,1,1,t);
}
}
int fnd2(int a , int b , int curr , int l , int r){
if(b < l || a > r){
return -1;
}
if(a <= l && b >= r){
// cout << cnt << " " << curr << " " << segment[curr].val << endl;
if(segment[curr].val != 0){
return -1;
}
while(curr < t){
push(curr);
if(segment[2*curr].val == 0){
curr = 2*curr;
}else{
curr = 2*curr+1;
}
}
return curr-t+1;
}
int mid = (l+r)/2;
push(curr);
int f = fnd2(a,b,2*curr,l,mid);
if(f != -1){
return f;
}
return fnd2(a,b,2*curr+1,mid+1,r);
}
int fnd(){
int pos = fnd2(1,n,1,1,t);
if(pos > 1){
if(pos >= k){
int f = fnd2(pos-k+1,pos-1,1,1,t);
if(f != -1){
return f;
}
}else{
int num = k-pos-1;
int f = fnd2(n-num,n,1,1,t);
if(f != -1){
return f;
}
f = fnd2(1,pos-1,1,1,t);
if(f != -1){
return f;
}
}
}else{
int f = fnd2(n-k+2,n,1,1,t);
if(f != -1){
return f;
}
}
return pos;
}
void init(int K , vector<int> r){
n = r.size() , cnt = 0 , k = K;
t = pow(2,ceil(log2(n)));
segment.resize(2*t,{0,0});
for(int i = 0 ; i < (int)r.size() ; i += 1){
upd(i+1,i+1,r[i],1,1,t);
}
for(int i = 0 ; i < n ; i += 1){
int f = fnd();
u(f);
}
}
int compare_plants(int x, int y){
if(val[x+1] < val[y+1]){
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... |