#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 2e5;
const int INF = 1e8;
int N, K, R[MAXN+10], H[MAXN+10];
struct SEG
{
pii tree[MAXN*4+10];
int lazy[MAXN*4+10];
void busy(int node, int tl, int tr)
{
tree[node].first+=lazy[node];
if(tl!=tr)
{
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
void init(int node, int tl, int tr)
{
if(tl==tr)
{
tree[node]={0, tl};
lazy[node]=0;
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
void update(int node, int tl, int tr, int l, int r, int k)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]+=k;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r, k);
update(node*2+1, mid+1, tr, l, r, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
void update2(int node, int tl, int tr, int p, int k)
{
busy(node, tl, tr);
if(tl==tr)
{
tree[node].first=k;
return;
}
int mid=tl+tr>>1;
if(p<=mid) update2(node*2, tl, mid, p, k);
else update2(node*2+1, mid+1, tr, p, k);
tree[node]=min(tree[node*2], tree[node*2+1]);
}
pii query(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return {INF, -1};
int mid=tl+tr>>1;
return min(query(node*2, tl, mid, l, r), query(node*2+1, mid+1, tr, l, r));
}
void query2(int node, int tl, int tr, int l, int r, vector<int> &V)
{
busy(node, tl, tr);
if(tree[node].first!=0) return;
if(r<tl || tr<l) return;
if(tl==tr)
{
V.push_back(tl);
return;
}
int mid=tl+tr>>1;
query2(node*2, tl, mid, l, r, V);
query2(node*2+1, mid+1, tr, l, r, V);
}
void init()
{
init(1, 0, N-1);
}
void update(int l, int r, int k)
{
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) update(1, 0, N-1, l, r, k);
else
{
update(1, 0, N-1, l, N-1, k);
update(1, 0, N-1, 0, r, k);
}
}
void update2(int p, int k)
{
p=(p%N+N)%N;
update2(1, 0, N-1, p, k);
}
pii query(int l, int r)
{
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) return query(1, 0, N-1, l, r);
else return min(query(1, 0, N-1, l, N-1), query(1, 0, N-1, 0, r));
}
vector<int> query2(int l, int r)
{
vector<int> ret;
l=(l%N+N)%N; r=(r%N+N)%N;
if(l<=r) query2(1, 0, N-1, l, r, ret);
else
{
query2(1, 0, N-1, l, N-1, ret);
query2(1, 0, N-1, 0, r, ret);
}
return ret;
}
}seg1, seg2, seg3;
int LL[MAXN*3+10], RR[MAXN*3+10];
int dist(int u, int v)
{
return min(abs(u-v), N-abs(u-v));
}
void init(int _K, vector<int> _R)
{
K=_K; N=_R.size();
for(int i=0; i<N; i++) R[i]=_R[i];
seg1.init(); seg2.init(); seg3.init();
for(int i=0; i<N; i++)
{
seg1.update2(i, R[i]);
seg2.update2(i, R[i]);
}
for(int i=0; i<N; i++) if(R[i]==0) seg1.update(i+1, i+K-1, 1);
for(int i=N-1; i>=0; i--)
{
vector<int> V;
assert(seg1.tree[1].first+seg1.lazy[1]==0);
int now=seg1.tree[1].second; H[now]=i;
assert(seg2.query(now-K+1, now-1).first>=1);
seg1.update(now+1, now+K-1, -1);
seg1.update2(now, INF);
seg2.update2(now, INF);
seg2.update(now-K+1, now-1, -1);
seg1.update(now-K+1, now-1, -1);
V=seg2.query2(now-K+1, now-1);
for(auto it : V) seg1.update(it+1, it+K-1, 1);
}
for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
vector<pii> V;
for(int i=0; i<N; i++) V.push_back({H[i], i});
sort(V.begin(), V.end(), greater<pii>());
for(int i=0; i<N; i++) seg3.update2(i, INF);
for(int i=0; i<3*N; i++) LL[i]=RR[i]=i;
for(int i=0; i<V.size(); i++)
{
int now=V[i].second;
pii t1=seg3.query(now-K+1, now), t2=seg3.query(now, now+K-1);
if(t1.first!=INF)
{
int p=t1.second;
if(now>p) p+=N;
LL[now+N]=min(LL[now+N], LL[p]);
RR[now+N]=max(RR[now+N], RR[p]);
}
if(t2.first!=INF)
{
int p=t2.second;
if(now>p) p+=N+N;
else p+=N;
LL[now+N]=min(LL[now+N], LL[p]);
RR[now+N]=max(RR[now+N], RR[p]);
}
LL[now]=LL[now+N]-N;
RR[now]=RR[now+N]-N;
LL[now+N+N]=LL[now+N]+N;
RR[now+N+N]=RR[now+N]+N;
LL[now]=max(LL[now], 0);
RR[now]=min(RR[now], 3*N-1);
seg3.update2(now, H[now]);
}
return;
}
bool f(int l, int r, int p)
{
p=(p%N+N)%N;
while(p<l) p+=N;
return p<=r;
}
int compare_plants(int x, int y)
{
if(f(LL[x], RR[x], y)) return -1;
if(f(LL[y], RR[y], x)) return 1;
return 0;
}
Compilation message
plants.cpp: In member function 'void SEG::init(int, int, int)':
plants.cpp:37:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
37 | int mid=tl+tr>>1;
| ~~^~~
plants.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
plants.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid=tl+tr>>1;
| ~~^~~
plants.cpp: In member function 'void SEG::update2(int, int, int, int, int)':
plants.cpp:65:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid=tl+tr>>1;
| ~~^~~
plants.cpp: In member function 'pii SEG::query(int, int, int, int, int)':
plants.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid=tl+tr>>1;
| ~~^~~
plants.cpp: In member function 'void SEG::query2(int, int, int, int, int, std::vector<int>&)':
plants.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid=tl+tr>>1;
| ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:166:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
166 | for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
| ^~~
plants.cpp:166:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
166 | for(int i=0; i<N; i++) printf("%d ", H[i]); printf("\n");
| ^~~~~~
plants.cpp:174:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
174 | for(int i=0; i<V.size(); i++)
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
19200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
