#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(),v.end()
#define SZ(a) ((int)a.size())
#define pb push_back
int seg1[800005],seg2[800005],lazy1[800005],lazy2[800005];
int layer[400005],tag[200005];
void build(int l,int r,int rt,const vector<int> &v,int *seg)
{
if(l==r)
return seg[rt]=v[l],void();
int mid=(l+r)>>1;
build(l,mid,rt<<1,v,seg),build(mid+1,r,rt<<1|1,v,seg);
seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}
void down(int rt,int *seg,int *lazy)
{
if(lazy[rt])
{
seg[rt<<1]+=lazy[rt],lazy[rt<<1]+=lazy[rt];
seg[rt<<1|1]+=lazy[rt],lazy[rt<<1|1]+=lazy[rt];
lazy[rt]=0;
}
}
void modify(int L,int R,int l,int r,int rt,int val,int *seg,int *lazy)
{
if(l!=r) down(rt,seg,lazy);
if(L<=l&&R>=r)
return lazy[rt]+=val,seg[rt]+=val,void();
int mid=(l+r)>>1;
if(L<=mid)
modify(L,R,l,mid,rt<<1,val,seg,lazy);
if(R>mid)
modify(L,R,mid+1,r,rt<<1|1,val,seg,lazy);
seg[rt]=min(seg[rt<<1],seg[rt<<1|1]);
}
int query(int l,int r,int rt,int *seg,int *lazy)
{
if(l!=r) down(rt,seg,lazy);
if(l==r)
return l;
int mid=(l+r)>>1;
if(seg[rt<<1]<=seg[rt<<1|1])
return query(l,mid,rt<<1,seg,lazy);
return query(mid+1,r,rt<<1|1,seg,lazy);
}
void dfs(int l,int r,int rt,int *seg,int *lazy,vector<int> &rst)
{
if(l!=r) down(rt,seg,lazy);
if(l==r)
return rst.pb(l);
int mid=(l+r)>>1;
if(seg[rt<<1]==0)
dfs(l,mid,rt<<1,seg,lazy,rst);
if(seg[rt<<1|1]==0)
dfs(mid+1,r,rt<<1|1,seg,lazy,rst);
}
const int INF=1e9;
int arr[200005],K,n;
void init(int k, vector<int> r)
{
n=SZ(r),K=k;
build(0,n-1,1,r,seg1),build(0,n-1,1,vector<int>(n,INF),seg2);
for(int i=0,ly=0;i<n;++ly)
{
while(seg1[1]==0)
{
int u=query(0,n-1,1,seg1,lazy1);
modify(u,u,0,n-1,1,INF,seg1,lazy1),modify(u,u,0,n-1,1,-INF,seg2,lazy2);
if(u+k<=n)
modify(u+1,u+k-1,0,n-1,1,1,seg2,lazy2);
else
{
if(u<n-1)
modify(u+1,n-1,0,n-1,1,1,seg2,lazy2);
modify(0,k-n+u-1,0,n-1,1,1,seg2,lazy2);
}
}
vector<int> rst;
dfs(0,n-1,1,seg2,lazy2,rst);
for(int u:rst)
{
if(u>=k-1)
modify(u-k+1,u,0,n-1,1,-1,seg1,lazy1);
else
modify(0,u,0,n-1,1,-1,seg1,lazy1),modify(n-(k-u-1),n-1,0,n-1,1,-1,seg1,lazy1);
if(u+k<=n)
modify(u+1,u+k-1,0,n-1,1,-1,seg2,lazy2);
else
{
if(u<n-1)
modify(u+1,n-1,0,n-1,1,-1,seg2,lazy2);
modify(0,k-n+u-1,0,n-1,1,-1,seg2,lazy2);
}
modify(u,u,0,n-1,1,INF,seg2,lazy2);
layer[u]=ly;
}
i+=SZ(rst);
}
layer[n]=layer[0];
deque<int> dq(1,0);
for(int i=1;i<n;++i)
{
if(dq.front()==i-k)
dq.pop_front();
if(dq.empty())
break;
if(layer[dq.front()]<layer[i])
{
tag[i]=1;
while(!dq.empty()&&layer[dq.back()]>=layer[i])
dq.pop_back();
dq.pb(i);
}
}
dq.clear(),dq.pb(n);
for(int i=n-1;i>0;--i)
{
if(dq.front()==i+k)
dq.pop_front();
if(dq.empty())
break;
if(layer[dq.front()]<layer[i])
{
tag[i]=1;
while(!dq.empty()&&layer[dq.back()]>=layer[i])
dq.pop_back();
dq.pb(i);
}
}
dq.clear(),dq.pb(0);
for(int i=1;i<n;++i)
{
if(dq.front()==i-k)
dq.pop_front();
if(dq.empty())
break;
if(layer[dq.front()]>layer[i])
{
tag[i]=-1;
while(!dq.empty()&&layer[dq.back()]<=layer[i])
dq.pop_back();
dq.pb(i);
}
}
dq.clear(),dq.pb(n);
for(int i=n-1;i>0;--i)
{
if(dq.front()==i+k)
dq.pop_front();
if(dq.empty())
break;
if(layer[dq.front()]>layer[i])
{
tag[i]=-1;
while(!dq.empty()&&layer[dq.back()]<=layer[i])
dq.pop_back();
dq.pb(i);
}
}
/*for(int i=0;i<n;++i)
cout << layer[i] << " \n"[i+1==n];
for(int i=0;i<n;++i)
cout << "[" << L[i] << "," << R[i] << "]" << " \n"[i+1==n];*/
}
int compare_plants(int x, int y)
{
if(layer[x]==layer[y]) return 0;
if(x==0)
return tag[y];
else
return layer[x]<layer[y]?1:-1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
90 ms |
3644 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
87 ms |
3576 KB |
Output is correct |
11 |
Correct |
85 ms |
3492 KB |
Output is correct |
12 |
Correct |
85 ms |
3704 KB |
Output is correct |
13 |
Correct |
89 ms |
3576 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
90 ms |
3644 KB |
Output is correct |
8 |
Correct |
3 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
640 KB |
Output is correct |
10 |
Correct |
87 ms |
3576 KB |
Output is correct |
11 |
Correct |
85 ms |
3492 KB |
Output is correct |
12 |
Correct |
85 ms |
3704 KB |
Output is correct |
13 |
Correct |
89 ms |
3576 KB |
Output is correct |
14 |
Correct |
151 ms |
4596 KB |
Output is correct |
15 |
Correct |
1120 ms |
14184 KB |
Output is correct |
16 |
Correct |
149 ms |
4572 KB |
Output is correct |
17 |
Correct |
1118 ms |
14088 KB |
Output is correct |
18 |
Correct |
783 ms |
14476 KB |
Output is correct |
19 |
Correct |
773 ms |
14440 KB |
Output is correct |
20 |
Correct |
996 ms |
14056 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
78 ms |
3320 KB |
Output is correct |
4 |
Correct |
559 ms |
13928 KB |
Output is correct |
5 |
Correct |
689 ms |
14148 KB |
Output is correct |
6 |
Correct |
907 ms |
14184 KB |
Output is correct |
7 |
Correct |
1066 ms |
14056 KB |
Output is correct |
8 |
Correct |
1162 ms |
14100 KB |
Output is correct |
9 |
Correct |
603 ms |
13500 KB |
Output is correct |
10 |
Correct |
612 ms |
14060 KB |
Output is correct |
11 |
Correct |
519 ms |
12964 KB |
Output is correct |
12 |
Correct |
724 ms |
14180 KB |
Output is correct |
13 |
Correct |
846 ms |
14400 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
810 ms |
13416 KB |
Output is correct |
7 |
Correct |
925 ms |
14056 KB |
Output is correct |
8 |
Correct |
1022 ms |
14212 KB |
Output is correct |
9 |
Correct |
1085 ms |
14184 KB |
Output is correct |
10 |
Correct |
570 ms |
13420 KB |
Output is correct |
11 |
Correct |
891 ms |
14236 KB |
Output is correct |
12 |
Correct |
540 ms |
14056 KB |
Output is correct |
13 |
Correct |
652 ms |
14068 KB |
Output is correct |
14 |
Correct |
896 ms |
14180 KB |
Output is correct |
15 |
Correct |
1018 ms |
14180 KB |
Output is correct |
16 |
Correct |
566 ms |
14056 KB |
Output is correct |
17 |
Correct |
668 ms |
13796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |