#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int st[1<<19], lz[1<<19];
void init(int i, int s, int e, vector<int> &r) {
if (s==e) {
st[i]=r[s-1];
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 spr(int i, bool b) {
if (st[i]<0) return ;
st[i]+=lz[i];
if (!b) for (auto &j:{i*2, i*2+1}) lz[j]+=lz[i];
lz[i]=0;
}
void getmax(int i, int s, int e, vector<int> &r) {
spr(i, s==e);
if (st[i]!=st[1]) return ;
if (s==e) { r.emplace_back(s); return ; }
int m=(s+e)/2;
getmax(i*2, s, m, r);
getmax(i*2+1, m+1, e, r);
}
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]=1;
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 erase(int i, int s, int e, vector<int> &r) {
spr(i, s==e);
if (r.empty()) return ;
if (s==e) { st[i]=-1; return ; }
int m=(s+e)/2;
vector<int> lv, rv;
for (auto &j:r) (j<=m?lv:rv).emplace_back(j);
erase(i*2, s, m, lv);
erase(i*2+1, m+1, e, rv);
st[i]=max(st[i*2], st[i*2+1]);
}
int N, K;
vector<int> lv;
vector<vector<pair<ll, int>>> L, R;
void init(int K, vector<int> r) {
::N=r.size();
::K=K;
for (auto &i:r) i=K-1-i;
init(1, 1, N, r);
lv.resize(N+1);
int t=0;
while (st[1]>=0) {
t++;
vector<int> k;
getmax(1, 1, N, k);
for (auto &i:k)
lv[i]=t,
upd(1, 1, N, max(1, i-K+1), i-1),
upd(1, 1, N, min(i-K+1+N, N+1), N);
erase(1, 1, N, k);
}
set<pair<int, int>> lr;
L.resize(N+1);
for (int i=N-K+2; i<=N; i++) lr.emplace(lv[i], i);
for (int i=1; i<=N; i++) {
auto k=lr.upper_bound({lv[i], 0});
if (k!=lr.end()) L[i].emplace_back((N+i-(k->second))%N, k->second);
int e=(i-K+N)%N+1;
lr.erase({lv[e], e});
lr.emplace(lv[i], i);
}
lr.clear();
R.resize(N+1);
for (int i=1; i<=K-1; i++) lr.emplace(lv[i], i);
for (int i=N; i>=1; i--) {
auto k=lr.upper_bound({lv[i], 0});
if (k!=lr.end()) R[i].emplace_back(((k->second)-i+N)%N, k->second);
int e=(i+K-2)%N+1;
lr.erase({lv[e], e});
lr.emplace(lv[i], i);
}
for (int j=1; j<20; j++) for (int i=1; i<=N; i++) {
if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
int e=L[i][j-1].second;
L[i].emplace_back(L[i][j-1].first+L[e][j-1].first, L[e][j-1].second);
}
if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
int e=R[i][j-1].second;
R[i].emplace_back(R[i][j-1].first+R[e][j-1].first, R[e][j-1].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) {
x++; 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:100: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]
100 | if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
| ~~~~~~~~~~~^~~
plants.cpp:100:49: 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]
100 | if (L[i].size()>=j&&L[L[i][j-1].second].size()>=j) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
plants.cpp:104: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]
104 | if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
| ~~~~~~~~~~~^~~
plants.cpp:104:49: 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]
104 | if (R[i].size()>=j&&R[R[i][j-1].second].size()>=j) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:116: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]
116 | if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
| ~~~~~~~~~~~^~
plants.cpp:117: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]
117 | if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
| ~~~~~~~~~~~^~
plants.cpp:119:40: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
119 | 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 |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 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 |
Runtime error |
60 ms |
9088 KB |
Execution killed with signal 11 |
| 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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 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 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 |
| 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 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
380 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
