#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<<18;
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];
}
pii query(int x, int lx, int rx, int l, int r){
propagate(x,lx,rx);
if(lx >= r or rx <= l) return d_neutral;
if(lx >= l and rx <= r) return tr[x];
int mid = (lx+rx)>>1;
return min(query(x<<1,lx,mid,l,r),query(x<<1|1,mid,rx,l,r));
}
pii query(int l, int r){
return query(1,0,N,l,r+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);
}
void init_st(){
fill(all(tr),d_neutral);
fill(all(lz),0);
}
vector<int> id;
vector<int> adj[N];
vector<bool> reach_from_0(N), reach_to_0(N);
vector<int> pref(2*N);
int n;
void init(int k, std::vector<int> a) {
k--;
n = sz(a);
id = vector<int>(n);
build(a);
int iter = 0;
rep(i,2*n){
pref[i] = a[i%n]+(i?pref[i-1]:0);
}
return;
int rem_cnt = 0;
auto rem = [&](int i){
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);
}
};
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});
}
}
init_st();
rep(i,n) id[i] = -id[i];
build(id);
{
queue<int> q;
q.push(0);
rupd(0,0,inf1);
while(!q.empty()){
int i = q.front();
q.pop();
reach_from_0[i] = 1;
vector<pii> ranges;
if(i+k < n){
ranges.pb({i+1,i+k});
}
else{
ranges.pb({i+1,n-1});
ranges.pb({0,(i+k)%n});
}
if(i-k >= 0){
ranges.pb({i-k,i-1});
}
else{
ranges.pb({0,i-k});
ranges.pb({i-k+n,n-1});
}
for(auto [l,r] : ranges){
if(l > r) conts;
while(true){
auto [mn,j] = query(l,r);
if(mn > n) break;
if(id[i] < id[j]) break;
q.push(j);
rupd(j,j,inf1);
}
}
}
}
init_st();
rep(i,n) id[i] = -id[i];
build(id);
{
queue<int> q;
q.push(0);
rupd(0,0,inf1);
while(!q.empty()){
int i = q.front();
q.pop();
reach_to_0[i] = 1;
vector<pii> ranges;
if(i+k < n){
ranges.pb({i+1,i+k});
}
else{
ranges.pb({i+1,n-1});
ranges.pb({0,(i+k)%n});
}
if(i-k >= 0){
ranges.pb({i-k,i-1});
}
else{
ranges.pb({0,i-k});
ranges.pb({i-k+n,n-1});
}
for(auto [l,r] : ranges){
if(l > r) conts;
while(true){
auto [mn,j] = query(l,r);
if(mn > n) break;
if(id[i] < id[j]) break;
q.push(j);
rupd(j,j,inf1);
}
}
}
}
}
int compare_plants(int x, int y) {
int add = 0;
if(y < x) y += n, add = n;
int cnt = pref[y-1]-pref[x];
if(cnt == 0) return 1;
y -= add;
if(x < y) x += n;
cnt = pref[x-1]-pref[y];
if(cnt == 0) return -1;
return 0;
// debug(dec_id[x]);
// debug(dec_id[y]);
// if(dec_id[x].ff == dec_id[y].ff){
// if(dec_id[x].ss < dec_id[y].ss){
// return 1;
// }
// else{
// return -1;
// }
// }
// if(inc_id[x].ff == inc_id[y].ff){
// if(inc_id[x].ss < inc_id[y].ss){
// return -1;
// }
// else{
// return 1;
// }
// }
// return 0;
// if(reach_from_0[y]) return 1;
// if(reach_to_0[y]) return -1;
// return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
21044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
20828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
20828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
20828 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
11 ms |
20824 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
20828 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
21044 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
