#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
using ar2 = array<int,2>;
const int mxN = (int)2e5+10;
const int INF = (int)1e9;
int n, k, h[mxN];
bitset<mxN> path[2];
vector<int> adj[mxN], radj[mxN];
template<class T, int SZ> struct SegTree{
T seg[SZ], lzy[SZ];
void init(){ fill(seg,seg+SZ,0), fill(lzy,lzy+SZ,0); }
void prop(int p, int l, int r){
if(!lzy[p] or l==r) return;
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
seg[p+1]+=lzy[p];
seg[rp]+=lzy[p];
lzy[p+1]+=lzy[p];
lzy[rp]+=lzy[p];
lzy[p]=0;
}
void upd(int i, int j, int v, int p=0, int l=0, int r=n-1){
if(i>r or j<l or i>j) return; prop(p,l,r);
if(i<=l and r<=j){ seg[p]+=v; lzy[p]+=v; return; }
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
if(i<=mid) upd(i,j,v,p+1,l,mid);
if(j>mid) upd(i,j,v,rp,mid+1,r);
seg[p] = min(seg[p+1],seg[rp]);
}
int findFirstMin(int i, int j, int p=0, int l=0, int r=n-1){
if(i>r or j<l or i>j) return -1; prop(p,l,r);
if(l==r) return l;
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
if(i>mid) return findFirstMin(i,j,rp,mid+1,r);
if(j<=mid) return findFirstMin(i,j,p+1,l,mid);
if(query(i,mid)==query(i,j)) return findFirstMin(i,j,p+1,l,mid);
return findFirstMin(i,j,rp,mid+1,r);
}
T query(int i, int j, int p=0, int l=0, int r=n-1){
if(j<l or i>r or i>j) return INF; prop(p,l,r);
if(i<=l and r<=j) return seg[p];
int mid = (l+r)/2; int rp = p+2*(mid-l+1);
return min(query(i,j,p+1,l,mid), query(i,j,rp,mid+1,r));
}
};
const int mxSeg = 2*mxN;
SegTree<int,mxSeg> segTree;
int cur;
void solve(int i){
bool ok = 1;
while(ok){
ok = 0;
if(i<k){
int i1 = segTree.findFirstMin(n-k+i,n-1);
if(i1!=-1 and !segTree.query(i1,i1)) solve(i1), ok=1;
}
int i1 = segTree.findFirstMin(max(0,i-k),i-1);
if(i1!=-1 and !segTree.query(i1,i1)) solve(i1), ok=1;
}
if(i<k){
segTree.upd(0,i-1,-1);
segTree.upd(n-k+i,n-1,-1);
}
else segTree.upd(i-k,i-1,-1);
segTree.upd(i,i,INF); h[i]=cur--;
}
int dis(int a, int b){ return min(abs(a-b),n-abs(a-b)); }
bitset<mxN> vis;
void dfs(int s){
vis[s]=1;
path[0][s]=1;
for(auto u : adj[s])
if(!vis[u]) dfs(u);
}
void dfs2(int s){
vis[s]=1;
path[1][s]=1;
for(auto u : radj[s])
if(!vis[u]) dfs2(u);
}
void init(int K, vector<int> r){
n = sz(r); k=K-1; segTree.init(); cur = n;
for(int i = 0; i < n; i++) segTree.upd(i,i,r[i]);
while(!segTree.query(0,n-1)) solve(segTree.findFirstMin(0,n-1));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if((i==j or h[i]>h[j]) and dis(i,j)<=k)
adj[i].pb(j), radj[j].pb(i);
dfs(0); vis.reset(); dfs2(0);
}
int compare_plants(int x, int y){
if(path[0][y]) return 1;
if(path[1][y]) return -1;
return 0;
}
Compilation message
plants.cpp: In member function 'void SegTree<T, SZ>::upd(int, int, int, int, int, int)':
plants.cpp:30:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
30 | if(i>r or j<l or i>j) return; prop(p,l,r);
| ^~
plants.cpp:30:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
30 | if(i>r or j<l or i>j) return; prop(p,l,r);
| ^~~~
plants.cpp: In member function 'int SegTree<T, SZ>::findFirstMin(int, int, int, int, int)':
plants.cpp:39:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
39 | if(i>r or j<l or i>j) return -1; prop(p,l,r);
| ^~
plants.cpp:39:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
39 | if(i>r or j<l or i>j) return -1; prop(p,l,r);
| ^~~~
plants.cpp: In member function 'T SegTree<T, SZ>::query(int, int, int, int, int)':
plants.cpp:49:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
49 | if(j<l or i>r or i>j) return INF; prop(p,l,r);
| ^~
plants.cpp:49:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
49 | if(j<l or i>r or i>j) return INF; prop(p,l,r);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12976 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 3 |
Correct |
3 ms |
12892 KB |
Output is correct |
| 4 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14172 KB |
Output is correct |
| 6 |
Execution timed out |
4100 ms |
32096 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12892 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12976 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
