//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
class SegmentTree{
public:
vector<int> st, lazy;
void merge(int i){
int l = 2 * i + 1, r = 2 * i + 2;
st[i] = min(st[l], st[r]);
}
void push(int i){
if(lazy[i]){
int l = 2 * i + 1, r = 2 * i + 2;
st[l] += lazy[i];
st[r] += lazy[i];
lazy[l] += lazy[i];
lazy[r] += lazy[i];
lazy[i] = 0;
}
}
void init_segtree(int n, vector<int>& a){
st.resize(4 * n);
lazy.resize(4 * n);
build(0, 0, n - 1, a);
}
void build(int i, int l, int r, vector<int>& a){
if(l == r){
st[i] = a[l];
} else{
int m = (l + r) / 2;
build(2 * i + 1, l, m, a);
build(2 * i + 2, m + 1, r, a);
merge(i);
}
}
int search(int i, int l, int r, int ql, int qr){
if(qr < l || ql > r){
return -1;
}
if(l == r){
return l;
}
push(i);
int m = (l + r) / 2;
int ans = -1;
if(st[2 * i + 1] == 0){
ans = search(2 * i + 1, l, m, ql, qr);
}
if(ans == -1 && st[2 * i + 2] == 0){
ans = search(2 * i + 2, m + 1, r, ql, qr);
}
return ans;
}
void set(int i, int l, int r, int p, int k){
if(l == r){
st[i] = k;
} else{
push(i);
int m = (l + r) / 2;
if(p <= m)
set(2 * i + 1, l, m, p, k);
else
set(2 * i + 2, m + 1, r, p, k);
merge(i);
}
}
void add(int i, int l, int r, int ql, int qr, int k){
if(ql <= l && r <= qr){
st[i] += k;
lazy[i] += k;
return;
}
if(qr < l || ql > r){
return;
}
push(i);
int m = (l + r) / 2;
add(2 * i + 1, l, m, ql, qr, k);
add(2 * i + 2, m + 1, r, ql, qr, k);
merge(i);
}
};
SegmentTree st;
int N, K;
vector<int> P;
int getpos(int l, int r){
if(0 <= l && r <= N - 1){
return st.search(0, 0, N - 1, l, r);
} else if(l < 0 && r < 0){
l += N, r += N;
return getpos(l, r);
} else{
return max(getpos(0, r), getpos(l + N, N - 1));
}
}
void decr(int l, int r){
if(0 <= l && r <= N - 1){
st.add(0, 0, N - 1, l, r, -1);
} else if(l < 0 && r < 0){
l += N, r += N;
decr(l, r);
} else{
decr(0, r);
decr(l + N, N - 1);
}
}
void ass(int i, int& n){
int l = i - K + 1, j = -1;
do{
j = getpos(l, i - 1);
if(j != -1)
ass(j, n);
} while(j != -1);
P[i] = n--;
st.set(0, 0, N - 1, i, INT_MAX);
decr(l, i - 1);
}
void build_P(){
P = vector<int>(N);
int n = N;
while(n){
int p = getpos(0, N - 1);
ass(p, n);
}
rep(i, 0, N) P.pb(P[i]);
N = SZ(P);
}
class MergeSortTree{
public:
vector<vector<pii>> st;
void init_merge_sort_tree(int n, vector<int>& a){
st.resize(4 * n);
build(0, 0, n - 1, a);
}
void build(int i, int l, int r, vector<int>& a){
if(l == r){
st[i].pb({a[l], l});
} else{
int m = (l + r) / 2;
build(2 * i + 1, l, m, a);
build(2 * i + 2, m + 1, r, a);
for(auto [x, pos] : st[2 * i + 1])
st[i].pb({x, pos});
for(auto [x, pos] : st[2 * i + 2])
st[i].pb({x, pos});
sort(all(st[i]));
}
}
pii search(int i, int l, int r, int ql, int qr, int x){
if(ql <= l && r <= qr){
int p = upper_bound(all(st[i]), make_pair(x, -1)) - st[i].begin() - 1;
if(p < 0){
return {-1, -1};
}
return st[i][p];
}
if(qr < l || ql > r){
return {-1, -1};
}
int m = (l + r) / 2;
pii p1 = search(2 * i + 1, l, m, ql, qr, x);
pii p2 = search(2 * i + 2, m + 1, r, ql, qr, x);
if(p1.ff > p2.ff){
return p1;
} else{
return p2;
}
}
};
MergeSortTree mst;
pii gethigher(int l, int r, int x){
if(0 <= l && r <= N - 1){
return mst.search(0, 0, N - 1, l, r, x);
} else if(l < 0 && r < 0){
l += N, r += N;
return gethigher(l, r, x);
} else if(l >= N && r >= N){
l -= N, r -= N;
return gethigher(l, r, x);
} else if(l < 0){
pii p1 = gethigher(0, r, x);
pii p2 = gethigher(l + N, N - 1, x);
if(p1.ff > p2.ff)
return p1;
return p2;
} else if(r >= N){
pii p1 = gethigher(l, N - 1, x);
pii p2 = gethigher(0, r - N, x);
if(p1.ff > p2.ff)
return p1;
return p2;
}
}
const int MAXK = 20;
vector<vector<int>> lt, rt;
void build_G(){
lt = rt = vector<vector<int>>(MAXK, vector<int>(N));
rep(i, 0, N){
rt[0][i] = mst.search(0, 0, N - 1, min(N - 1, i + 1), min(N - 1, i + K - 1), P[i]).ss; //gethigher(i + 1, i + K - 1, P[i]).ss;
lt[0][i] = mst.search(0, 0, N - 1, max(0, i - K + 1), max(0, i - 1), P[i]).ss; //gethigher(i - K + 1, i - 1, P[i]).ss;
if(rt[0][i] < 0) rt[0][i] = i;
if(lt[0][i] < 0) lt[0][i] = i;
}
rep(k, 1, MAXK){
rep(i, 0, N){
rt[k][i] = rt[k - 1][rt[k - 1][i]];
lt[k][i] = lt[k - 1][lt[k - 1][i]];
}
}
}
void init(int k, vector<int> r){
N = SZ(r), K = k;
st.init_segtree(N, r);
build_P();
mst.init_merge_sort_tree(N, P);
build_G();
}
int compare_plants(int x, int y){
if(x < y){
int v = x;
per(k, MAXK - 1, 0){
if(rt[k][v] < y){
v = rt[k][v];
}
}
v = rt[0][v];
if(v >= y){
if(P[v] >= P[y]) return 1;
else return -1;
}
x += N / 2;
v = x;
per(k, MAXK - 1, 0){
if(y < lt[k][v]){
v = lt[k][v];
}
}
v = lt[0][v];
if(v <= y){
if(P[v] >= P[y]) return 1;
else return -1;
}
} else if(y < x){
int v = x;
per(k, MAXK - 1, 0){
if(y < lt[k][v]){
v = lt[k][v];
}
}
v = lt[0][v];
if(v <= y){
if(P[v] >= P[y]) return 1;
else return -1;
}
y += N / 2;
v = x;
per(k, MAXK - 1, 0){
if(rt[k][v] < y){
v = rt[k][v];
}
}
v = rt[0][v];
if(y <= v){
if(P[v] >= P[y]) return 1;
else return -1;
}
}
return 0;
}
Compilation message
plants.cpp: In member function 'void MergeSortTree::build(int, int, int, std::vector<int>&)':
plants.cpp:163:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
163 | for(auto [x, pos] : st[2 * i + 1])
| ^
plants.cpp:165:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
165 | for(auto [x, pos] : st[2 * i + 2])
| ^
plants.cpp: In function 'std::pair<int, int> gethigher(int, int, int)':
plants.cpp:216:1: warning: control reaches end of non-void function [-Wreturn-type]
216 | }
| ^
| # |
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 |
256 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 |
256 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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 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 |
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 |
384 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
384 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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
