#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define pb push_back
#define endl '\n'
#define conts continue
#define sz(a) (int)a.size()
#define ff first
#define ss second
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; ++i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &x, T y){
x = min(x,y);
}
template<typename T>
void amax(T &x, T y){
x = max(x,y);
}
template<typename A,typename B>
string to_string(pair<A,B> p);
string to_string(const string &s){
return "'"+s+"'";
}
string to_string(const char* s){
return to_string((string)s);
}
string to_string(bool b){
return b?"true":"false";
}
template<typename A>
string to_string(A v){
string res = "{";
trav(x,v){
res += to_string(x)+",";
}
if(res.back() == ',') res.pop_back();
res += "}";
return res;
}
template<typename A,typename B>
string to_string(pair<A,B> p){
return "("+to_string(p.ff)+","+to_string(p.ss)+")";
}
#define debug(x) cout << "[" << #x << "]: "; cout << to_string(x) << endl
const int MOD = 1e9 + 7;
const int N = 1<<15;
const int inf1 = 1e9 + 5;
const ll inf2 = (ll)1e18 + 5;
#include "plants.h"
pii d_neutral = {inf1,-1};
vector<pii> tr(4*N,d_neutral);
vector<int> lz(4*N);
void propagate(int x, int lx, int rx){
int v = lz[x];
tr[x].ff += v;
if(rx-lx > 1){
lz[x<<1] += v;
lz[x<<1|1] += v;
}
lz[x] = 0;
}
void rupd(int x, int lx, int rx, int l, int r, int v){
propagate(x,lx,rx);
if(lx >= r or rx <= l) return;
if(lx >= l and rx <= r){
lz[x] = v;
propagate(x,lx,rx);
return;
}
int mid = (lx+rx)>>1;
rupd(x<<1,lx,mid,l,r,v);
rupd(x<<1|1,mid,rx,l,r,v);
tr[x] = min(tr[x<<1],tr[x<<1|1]);
}
void rupd(int l, int r, int v){
rupd(1,0,N,l,r+1,v);
}
pii query(){
propagate(1,0,N);
return tr[1];
}
void build(int x, int lx, int rx, vector<int> &a){
if(rx-lx == 1){
if(lx < sz(a)){
tr[x] = {a[lx],lx};
}
return;
}
int mid = (lx+rx) >> 1;
build(x<<1,lx,mid,a);
build(x<<1|1,mid,rx,a);
tr[x] = min(tr[x<<1],tr[x<<1|1]);
}
void build(vector<int> &a){
build(1,0,N,a);
}
vector<int> id(N);
vector<int> adj[N];
bool reach[N][N];
void dfs(int u, int s){
reach[s][u] = 1;
trav(v,adj[u]){
if(reach[s][v]) conts;
dfs(v,s);
}
}
void init(int k, std::vector<int> a) {
k--;
int n = sz(a);
build(a);
int iter = 0;
int rem_cnt = 0;
vector<bool> remm(n);
auto rem = [&](int i){
remm[i] = 1;
rem_cnt++;
id[i] = iter;
if(i-k >= 0){
rupd(i-k,i-1,-1);
}
else{
rupd(0,i-1,-1);
rupd(i-k+n,n-1,-1);
}
int j = i;
rep1(x,k){
j = (j+1)%n;
if(!remm[j]){
adj[i].pb(j);
}
}
};
set<int> zeros;
set<pii> dis;
while(rem_cnt < n){
iter++;
while(true){
auto [mn,i] = query();
if(mn == 0){
rupd(i,i,inf1);
zeros.insert(i);
auto it = zeros.find(i);
int prevv = -1, nxt = -1;
if(it != zeros.begin()){
prevv = *prev(it);
}
if(next(it) != zeros.end()){
nxt = *next(it);
}
if(prevv != -1 and nxt != -1) dis.erase({nxt-prevv,nxt});
if(prevv != -1) dis.insert({i-prevv,i});
if(nxt != -1) dis.insert({nxt-i,nxt});
}
else{
break;
}
}
if(sz(zeros) == 1){
trav(i,zeros){
rem(i);
}
zeros.clear();
dis.clear();
conts;
}
vector<int> del;
{
int i = *zeros.begin(), j = *zeros.rbegin();
int d = (i-j+n)%n;
if(d > k){
del.pb(i);
}
}
for(auto it = dis.rbegin(); it != dis.rend(); ++it){
auto [d,i] = *it;
if(d > k){
del.pb(i);
}
else{
break;
}
}
trav(i,del){
rem(i);
auto it = zeros.find(i);
int prevv = -1, nxt = -1;
if(it != zeros.begin()){
prevv = *prev(it);
}
if(next(it) != zeros.end()){
nxt = *next(it);
}
zeros.erase(it);
if(prevv != -1) dis.erase({i-prevv,i});
if(nxt != -1) dis.erase({nxt-i,nxt});
if(prevv != -1 and nxt != -1) dis.insert({nxt-prevv,nxt});
}
}
rep(i,n){
dfs(i,i);
}
}
int compare_plants(int x, int y) {
if(reach[x][y]) return 1;
if(reach[y][x]) return -1;
return 0;
if(id[x] < id[y]) return 1;
if(id[x] > id[y]) return -1;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
4696 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
