#include "plants.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define rank fuck
using namespace std;
using lint = long long;
using llf = long double;
using pi = pair<lint, lint>;
const int MAXN = 200005;
const int MAXT = 2100005;
int n, rank[MAXN];
lint DL[18][MAXN], DR[18][MAXN];
int L[18][MAXN], R[18][MAXN];
vector<int> lev[MAXN];
struct node{
int minv;
int lidx, ridx;
node(){
minv = 1e9;
}
node(int x, int v){
lidx = ridx = x;
minv = v;
}
node operator+(const node &n)const{
node x = *this;
node y = n;
if(x.minv < y.minv) return x;
if(x.minv > y.minv) return y;
x.lidx = min(x.lidx, y.lidx);
x.ridx = max(x.ridx, y.ridx);
return x;
}
};
struct seg{
node tree[MAXT];
int lim;
void init(int n){
for(lim = 1; lim <= 3 * n; lim <<= 1);
for(int i=0; i<3*n; i++) tree[i + lim] = node(i-n, 1e9);
for(int i=lim-1; i; i--) tree[i] = tree[2*i] + tree[2*i+1];
}
void upd(int x, int v){
node val(x, v);
x += n + lim;
tree[x] = val;
while(x > 1){
x >>= 1;
tree[x] = tree[2*x] + tree[2*x+1];
}
}
node query(int s, int e){
s += lim + n;
e += lim + n;
node ret;
while(s < e){
if(s%2 == 1) ret = ret + tree[s++];
if(e%2 == 0) ret = ret + tree[e--];
s >>= 1;
e >>= 1;
}
if(s == e) ret = ret + tree[s];
return ret;
}
}seg;
void init(int k, std::vector<int> r) {
n = sz(r);
int layer = 0;
while(count(rank, rank + n, 0)){
vector<int> vect;
for(int j=0; j<n; j++){
if(r[j]) continue;
bool claim = true;
for(int x=1; x<=k-1; x++){
if(r[(j-x+n)%n] == 0) claim = false;
}
if(claim) vect.push_back(j);
}
layer++;
for(auto &j : vect) if(!rank[j]) rank[j] = layer;
for(auto &j : vect){
r[j] = k - 1;
for(int x=1; x<=k-1; x++){
r[(j-x+n)%n]--;
}
}
}
for(int i=0; i<n; i++){
printf("%d ", rank[i]);
lev[rank[i]].push_back(i);
}
puts("");
seg.init(3*n);
for(int i=layer; i; i--){
for(auto &j : lev[i]){
auto qr = seg.query(j-k+1, j+k-1);
L[0][j] = R[0][j] = j;
if(qr.minv > 1e8) continue;
L[0][j] = (qr.lidx + n) % n;
R[0][j] = (qr.ridx + n) % n;
DL[0][j] = (j - L[0][j] + n) % n;
DR[0][j] = (R[0][j] - j + n) % n;
}
for(auto &j : lev[i]){
seg.upd(j - n, i);
seg.upd(j , i);
seg.upd(j + n, i);
}
}
for(int i=1; i<18; i++){
for(int j=0; j<n; j++){
L[i][j] = L[i-1][L[i-1][j]];
R[i][j] = R[i-1][R[i-1][j]];
DL[i][j] = DL[i-1][j] + DL[i-1][L[i-1][j]];
DR[i][j] = DR[i-1][j] + DR[i-1][R[i-1][j]];
}
}
}
int compare_plants(int x, int y) {
if(rank[x] == rank[y]) return 0;
if(rank[x] > rank[y]) return -compare_plants(y, x);
lint st = x, ed = x;
{
lint dist = 0;
int p = x;
for(int i=17; i>=0; i--){
if(rank[L[i][p]] < rank[y]){
dist += DL[i][p];
p = L[i][p];
}
}
dist += DL[0][p];
st = x - dist;
}
{
lint dist = 0;
int p = x;
for(int i=17; i>=0; i--){
if(rank[R[i][p]] < rank[y]){
dist += DR[i][p];
p = R[i][p];
}
}
dist += DR[0][p];
ed = x + dist;
}
lint Q = ed - ed % n + y;
if(Q > ed) Q -= n;
return Q >= st;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
30112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
30080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
