#include "bits/stdc++.h"
#include "plants.h"
using namespace std;
#define int long long
pair<int,int> seg[800001];
int lazy[800001];
vector<int> arr;
void build(int p,int l,int r){
if(l==r){
seg[p] = {arr[l],l};
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
seg[p].first+=lazy[p];
if(l!=r){
lazy[p*2]+=lazy[p];
lazy[p*2+1]+=lazy[p];
}
lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
prop(p,l,r);
if(l>=lq&&r<=rq){
lazy[p]+=val;
prop(p,l,r);
return ;
}
if(r<lq||l>rq)return ;
int md = (l+r)/2;
update(p*2,l,md,lq,rq,val);
update(p*2+1,md+1,r,lq,rq,val);
seg[p] = min(seg[p*2],seg[p*2+1]);
}
pair<int,int> query(int p,int l,int r,int lq,int rq){
prop(p,l,r);
if(l>=lq&&r<=rq)return seg[p];
if(r<lq||l>rq)return {1e9,0};
int md = (l+r)/2;
return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int idx = 0,k,n;
vector<int> h;
int bad(int x){
int l = x-k+1 , r = x-1;
if(r==-1){
l+=n;r+=n;
pair<int,int> val = query(1,0,n-1,l,r);
if(val.first==0)return val.second;
return -1;
}else{
pair<int,int> val = query(1,0,n-1,max(0ll,l),r);
if(l<0){
l+=n;
val = min(val,query(1,0,n-1,l,n-1));
}
if(val.first==0)return val.second;
return -1;
}
}
void fix(){
pair<int,int> x = query(1,0,n-1,0,n-1);
if(x.first<0){
update(1,0,n-1,x.second,x.second,1e9);
}else return ;
fix();
}
void buld(int x){
while(bad(x)!=-1){
buld(bad(x));
}
int l = x-k+1 , r = x;
update(1,0,n-1,max(0ll,l),r,-1);
if(l<0){
l+=n;
update(1,0,n-1,l,n-1,-1);
}
h[x] = idx--;
fix();
}
int li[200001][20];
int ri[200001][20];
int PL[200001][20];
int PR[200001][20];
void init(int32_t K, vector<int32_t> r){
idx = r.size();
n = r.size();
k = K;
for(int i = 0;i<n;i++){
arr.push_back(r[i]);
h.push_back(-1);
}
build(1,0,n-1);
while(seg[1].first==0){
buld(seg[1].second);
}
for(int i = 0;i<n;i++){
if(h[i]==-1){
assert(0);
}
}
multiset<pair<int,int>> s;
for(int i = 0;i<k-1;i++){
s.insert({h[i],i});
}
for(int i = n-1;i>=0;i--){
auto it = s.lower_bound(make_pair(h[i],0));
if(it==s.begin()){
ri[i][0] = 0;
PR[i][0] = 0;
}else{
it--;
PR[i][0] = (*it).second;
ri[i][0] = ((*it).second-i+n)%n;
}
int nah = (i+k-1)%n;
s.erase(s.lower_bound(make_pair(h[nah],nah)));
s.insert({h[i],i});
}
s.clear();
for(int i = n-k+1;i<n;i++){
s.insert({h[i],i});
}
for(int i = 0;i<n;i++){
auto it = s.lower_bound(make_pair(h[i],0));
if(it==s.begin()){
li[i][0] = 0;
PL[i][0] = i;
}else{
it--;
PL[i][0] = (*it).second;
li[i][0] = (i-(*it).second+n)%n;
}
int nah = (i-k+1+n)%n;
s.erase(s.lower_bound(make_pair(h[nah],nah)));
s.insert({h[i],i});
}
for(int j = 1;j<20;j++){
for(int i = 0;i<n;i++){
PL[i][j] = PL[PL[i][j-1]][j-1];
PR[i][j] = PR[PR[i][j-1]][j-1];
li[i][j] = li[i][j-1]+li[PL[i][j-1]][j-1];
ri[i][j] = ri[i][j-1]+ri[PR[i][j-1]][j-1];
}
}
}
int32_t compare_plants(int32_t x, int32_t y){
int st = x;
int cur = x;
for(int i = 19;i>=0;i--){
if(st+ri[cur][i]<y){
st+=ri[cur][i];
cur = PR[cur][i];
}
}
st+=ri[st][0];
if(st>=y&&h[y]<=h[st%n])return 1;
st = y;
cur = y;
for(int i = 19;i>=0;i--){
if(st-li[cur][i]>x){
st -= li[cur][i];
cur = PL[cur][i];
}
}
st -= li[st][0];
if(st<=x&&h[x]<=h[(st+n)%n])return -1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 2 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 3 |
Incorrect |
53 ms |
15608 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10584 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10588 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
