#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K;
int st[1<<19], lz[1<<19];
void spr(int i, bool b) {
st[i]+=lz[i];
if (!b) for (auto &j:{i*2, i*2+1}) lz[j]+=lz[i];
lz[i]=0;
}
void init(int i, int s, int e, vector<int> &r) {
if (s==e) { st[i]=r[s]; return ; }
int m=(s+e)/2;
init(i*2, s, m, r);
init(i*2+1, m+1, e, r);
st[i]=max(st[i*2], st[i*2+1]);
}
void upd(int i, int s, int e, int l, int r) {
spr(i, s==e);
if (e<l||r<s||r<l) return ;
if (l<=s&&e<=r) {
lz[i]++;
spr(i, s==e);
return ;
}
int m=(s+e)/2;
upd(i*2, s, m, l, r);
upd(i*2+1, m+1, e, l, r);
st[i]=max(st[i*2], st[i*2+1]);
}
void del(int i, int s, int e, vector<int> &v) {
spr(i, s==e);
if (v.empty()) return ;
if (s==e) {
st[i]=-(1e9);
return ;
}
int m=(s+e)/2;
vector<int> lv, rv;
for (auto &j:v) (j<=m?lv:rv).emplace_back(j);
del(i*2, s, m, lv);
del(i*2+1, m+1, e, rv);
st[i]=max(st[i*2], st[i*2+1]);
}
int get(int i, int s, int e, int l, int r) {
spr(i, s==e);
if (st[i]!=K-1||e<l||r<s||r<l) return -1;
if (s==e) return s;
int m=(s+e)/2, v=get(i*2, s, m, l, r);
return v!=-1?v:get(i*2+1, m+1, e, l, r);
}
int get(int l, int r) {
if (l<0) {
int v=get(1, 0, N-1, l+N, N-1);
return v!=-1?v:get(1, 0, N-1, 0, r);
}
if (r>=N) {
int v=get(1, 0, N-1, l, N-1);
return v!=-1?v:get(1, 0, N-1, 0, r-N);
}
return get(1, 0, N-1, l, r);
}
vector<int> lv;
vector<vector<pair<ll, int>>> L, R;
void init(int K, vector<int> r) {
auto val = [&](int x) {
if (get(x, x)==-1||get(x-K+1, x-1)!=-1) return false;
return true;
};
auto upd = [&](int l, int r) {
if (l<0) {
::upd(1, 0, N-1, 0, r);
::upd(1, 0, N-1, l+N, N-1);
}
else ::upd(1, 0, N-1, l, r);
};
::N=r.size(), ::K=K;
for (auto &i:r) i=K-1-i;
init(1, 0, N-1, r);
lv.resize(N);
int t=0;
vector<int> lg;
for (int i=0; i<N; i++) if (val(i)) lg.emplace_back(i);
while (st[1]>=0) {
++t;
//assert(st[1]==K-1);
for (auto &i:lg) {
assert(lv[i]==0||lv[i]==t);
if (lv[i]) continue;
lv[i]=t;
upd(i-K+1, i-1);
}
del(1, 0, N-1, lg);
vector<int> nx;
for (auto &i:lg) {
int li=get(i-K+1, i-1), ri=get(i+1, i+K-1);
if (li!=-1&&val(li)) nx.emplace_back(li);
if (ri!=-1&&val(ri)) nx.emplace_back(li);
}
swap(lg, nx);
}
L.resize(N);
R.resize(N);
set<pair<ll, int>> lr;
for (int i=N-K+1; i<N; i++) lr.emplace(lv[i], i);
for (int i=0; i<N; i++) {
auto k=lr.lower_bound({lv[i], i});
if (k!=lr.end()) L[i].emplace_back((i-(k->second)+N)%N, k->second);
int b=(i-K+1+N)%N;
lr.erase({lv[b], b});
lr.emplace(lv[i], i);
}
lr.clear();
for (int i=0; i<K-1; i++) lr.emplace(lv[i], i);
for (int i=N-1; i>=0; i--) {
auto k=lr.lower_bound({lv[i], i});
if (k!=lr.end()) L[i].emplace_back(((k->second)-i+N)%N, k->second);
int b=(i+K-1)%N;
lr.erase({lv[b], b});
lr.emplace(lv[i], i);
}
for (int j=0; j<20; j++) for (int i=0; i<N; i++) {
if (L[i].size()>j&&L[L[i][j].second].size()>j) {
int b=L[i][j].second;
L[i].emplace_back(L[b][j].first+L[i][j].first, L[b][j].second);
}
if (R[i].size()>j&&R[R[i][j].second].size()>j) {
int b=R[i][j].second;
R[i].emplace_back(R[b][j].first+R[i][j].first, R[b][j].second);
}
}
}
bool cmp(int x, int y) {
if (lv[x]>=lv[y]) return false;
int l=x, r=x;
ll ld=0, rd=0;
for (int i=19; i>=0; i--) {
if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
}
for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
return false;
}
int compare_plants(int x, int y) {
if (cmp(x, y)) return 1;
if (cmp(y, x)) return -1;
return 0;
}
Compilation message
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:132:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
132 | if (L[i].size()>j&&L[L[i][j].second].size()>j) {
| ~~~~~~~~~~~^~
plants.cpp:132:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
132 | if (L[i].size()>j&&L[L[i][j].second].size()>j) {
| ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp:136:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
136 | if (R[i].size()>j&&R[R[i][j].second].size()>j) {
| ~~~~~~~~~~~^~
plants.cpp:136:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
136 | if (R[i].size()>j&&R[R[i][j].second].size()>j) {
| ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:148:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
148 | if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
| ~~~~~~~~~~~^~
plants.cpp:149:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
149 | if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
| ~~~~~~~~~~~^~
plants.cpp:151:40: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
151 | for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
| ~~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Execution timed out |
4046 ms |
364 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Execution timed out |
4066 ms |
364 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Execution timed out |
4066 ms |
364 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4065 ms |
512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Execution timed out |
4072 ms |
364 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Execution timed out |
4073 ms |
364 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Execution timed out |
4046 ms |
364 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
