#include "plants.h"
//Bismillahirrahmanirrahim
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#include <bits/stdc++.h>
using namespace std;
typedef long long lo;
typedef pair< lo,lo > PII;
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=0;i<n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)
const lo inf = 2000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 200005;
const lo mod = 1000000007;
int m,b[li],a[li],flag,t,siz[li],say,vis[li],dep[li],kk,lazy[li*4];
int cev;
PII tree[li*4];
string s;
vector<int> v[li],vv;
inline void build(int node,int start,int end){
if(start==end){
tree[node]={vv[start],start};
return ;
}
build(node*2,start,mid),build(node*2+1,mid+1,end);
tree[node].fi=min(tree[node*2].fi,tree[node*2+1].fi);
}
inline void push(int node,int start,int end){
if(lazy[node]==0)return;
tree[node].fi+=lazy[node];
if(start!=end){
lazy[node*2]+=lazy[node];
lazy[node*2+1]+=lazy[node];
}
lazy[node]=0;
}
inline void update(int node,int start,int end,int l,int r){
push(node,start,end);
if(start>end || start>r || end<l || l>r)return;
if(start>=l && end<=r){
lazy[node]--;
push(node,start,end);
return;
}
update(node*2,start,mid+1,l,r),update(node*2+1,mid+1,end,l,r);
tree[node]=min(tree[node*2],tree[node*2+1]);
}
inline void update2(int node,int start,int end,int l,int r){
push(node,start,end);
if(start>end || start>r || end<l || l>r)return;
if(start>=l && end<=r){
tree[node].fi=inf;
return;
}
update(node*2,start,mid+1,l,r),update(node*2+1,mid+1,end,l,r);
tree[node]=min(tree[node*2],tree[node*2+1]);
}
inline PII query(int node,int start,int end,int l,int r){
if(start>end || start>r || end<l || l>r)return {inf,inf};
push(node,start,end);
if(start>=l && end<=r)return tree[node];
return max(query(node*2,start,mid+1,l,r),query(node*2+1,mid+1,end,l,r));
}
inline void dfs(int node,int der){
if(vis[node])return;
vis[node]=say;
dep[node]=der;
for(int i=0;i<(int)v[node].size();i++){
int go=v[node][i];
dfs(go,der+1);
}
}
void init(int k, std::vector<int> r) {
for(int i=0;i<(int)r.size();i++){
if(r[i]==1){
v[(i+1)%(int)r.size()].pb(i);
siz[i]++;
}
}
//~ queue<int>
//~ int n=(int)r.size();
//~ FOR{
//~ if(siz[i]==0){
//~ say++;
//~ dfs(i,0);
//~ }
//~ }
vv.pb(0);
for(int i=0;i<(int)r.size();i++)vv.pb(r[i]);
//~ vv=r;
say=0;
kk=k;
int n=(int)vv.size();
build(1,1,n);
for(int i=1;i<(int)vv.size();i++){
int ind=-1;
ind=query(1,1,n,1,n).se;
while(1){
flag=0;
while(query(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1).fi==0){ind=query(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1).se;flag=1;}
while(query(1,1,n,max(ind+1,ind-k+1+n),n).fi==0){ind=query(1,1,n,max(ind+1,ind-k+1+n),n).se;flag=1;}
if(!flag)break;
}
update(1,1,n,max(1,min(ind-1,ind-k+1)),ind-1);
update(1,1,n,max(ind+1,ind-k+1+n),n);
update2(1,1,n,ind,ind);
vis[ind]=++say;
continue;
}
}
int compare_plants(int x, int y) {
x++;
y++;
if(vis[x]<vis[y])return 1;
if(vis[x]>vis[y])return -1;
if(vis[x]==vis[y]){
//~ cout<<x<<" : : "<<y<<" : ;"<<vis[x]<<" : : "<<vis[y]<<endl;
return 0;
}
if(vis[x]!=vis[y])return 0;
if(dep[x]>dep[y])return -1;
return 1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9980 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
11 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9984 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
