#include<bits/stdc++.h>
using namespace std;
#include "plants.h"
const int N = 2e5 + 10, M = 20;
int p[N], rev_p[N];
int f[M + 1][2 * N], g[M + 1][2 * N];
struct IT1 {
int T[N << 2], lazy[N << 2];;
void push(int s, int l, int r) {
if (!lazy[s]) return;
T[s] += lazy[s];
if (l != r) {
lazy[s << 1] += lazy[s];
lazy[s << 1 | 1] += lazy[s];
}
lazy[s] = 0;
}
void up(int s, int l, int r, int from, int to, int val) {
push(s, l, r);
if (l > to || r < from) return;
if (from <= l && r <= to) {
lazy[s] = val;
push(s, l, r);
return;
}
int mid = l + r >> 1;
up(s << 1, l, mid, from, to, val);
up(s << 1 | 1, mid + 1, r, from, to, val);
T[s] = min(T[s << 1], T[s << 1 | 1]);
}
int get(int s, int l, int r, int from, int to) {
push(s, l, r);
if (l > to || r < from || T[s]) return -1;
if (l == r) return l;
int mid = l + r >> 1;
int ret = get(s << 1 | 1, mid + 1, r, from, to);
if (ret >= 0) return ret;
return get(s << 1, l, mid, from, to);
}
} it1;
struct IT2 {
int T[N << 3];
void up(int s, int l, int r, int pos, int val) {
if (l == r) {
T[s] = val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) up(s << 1, l, mid, pos, val);
else up(s << 1 | 1, mid + 1, r, pos, val);
T[s] = max(T[s << 1], T[s << 1 | 1]);
}
int get(int s, int l, int r, int from, int to) {
if (l > to || r < from) return -1;
if (from <= l && r <= to) return T[s];
int mid = l + r >> 1;
return max(get(s << 1, l, mid, from, to), get(s << 1 | 1, mid + 1, r, from, to));
}
} it2;
int n;
void init(int k, std::vector<int> r) {
n = r.size();
k--;
for(int i = 0; i < n; i++) it1.up(1, 0, n - 1, i, i, r[i]);
int val = n - 1;
auto calc = [&] () {
int m = n;
vector<int> ret(m);
for(int i = 0; i < m; i++) {
for(int j = i; j <= i + k; j++) ret[i] += p[i] < p[j % m];
}
return ret;
};
auto dfs = [&] (auto self, int i) -> void {
while (1) {
int left = it1.get(1, 0, n - 1, max(0, i - k), i - 1);
if (left >= 0) self(self, left);
else if (i - k < 0) {
left = it1.get(1, 0, n - 1, n + i - k, n - 1);
if (left >= 0) self(self, left);
else break;
}
else break;
}
p[i] = val--;
it1.up(1, 0, n - 1, i, i, 1e9);
it1.up(1, 0, n - 1, max(0, i - k), i - 1, -1);
if (i - k < 0) it1.up(1, 0, n - 1, n + i - k, n - 1, -1);
};
while (1) {
int pos = it1.get(1, 0, n - 1, 0, n - 1);
if (pos < 0) break;
dfs(dfs, pos);
}
for(int i = 0; i < n; i++) rev_p[p[i]] = i;
for(int i = 0; i < n; i++) p[i + n] = p[i];
for(int i = 0; i <= 4 * 2 * n; i++) it2.T[i] = -1;
for(int val = 0; val < n; val++) {
int largest;
int i = rev_p[val];
// cout << i << endl;
largest = it2.get(1, 0, 2 * n - 1, i + 1, min(2 * n - 1, i + k));
f[0][i] = largest >= 0 ? rev_p[largest] : -1;
largest = it2.get(1, 0, 2 * n - 1, max(0, i - k), i - 1);
g[0][i] = largest >= 0 ? rev_p[largest] : -1;
it2.up(1, 0, 2 * n - 1, i, val);
i += n;
largest = it2.get(1, 0, 2 * n - 1, i + 1, min(2 * n - 1, i + k));
f[0][i] = largest >= 0 ? rev_p[largest] : -1;
largest = it2.get(1, 0, 2 * n - 1, max(0, i - k), i - 1);
g[0][i] = largest >= 0 ? rev_p[largest] : -1;
it2.up(1, 0, 2 * n - 1, i, val);
}
for(int j = 1; j <= M; j++) for(int i = 0; i < 2 * n; i++) {
if (f[j - 1][i] < 0) f[j][i] = -1;
else f[j][i] = f[j - 1][f[j - 1][i]];
if (g[j - 1][i] < 0) g[j][i] = -1;
else g[j][i] = g[j - 1][g[j - 1][i]];
}
// for(int i = 0; i < n; i++) cout << p[i] << " "; cout << endl;
// cout << f[0][1] << endl;
// exit(0);
}
int move_right (int i, int val) {
for(int j = M; j >= 0; j--) {
if (f[j][i] >= 0 && p[f[j][i]] >= val) i = f[j][i];
}
return i;
}
int move_left (int i, int val) {
for(int j = M; j >= 0; j--) {
if (g[j][i] >= 0 && p[g[j][i]] >= val) i = g[j][i];
}
return i;
}
int compare_plants(int x, int y) {
int ret = 1;
if (p[x] < p[y]) ret = -1, swap(x, y);
if (x < y) x += n;
if (move_left(x, p[y]) <= y) return ret;
if (move_right(x, p[y]) >= y + n) return ret;
return 0;
}
#ifdef ngu
int main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
assert(scanf("%d%d%d", &n, &k, &q) == 3);
r.resize(n);
answer.resize(q);
for (int i = 0; i < n; i++) {
int value;
assert(scanf("%d", &value) == 1);
r[i] = value;
}
x.resize(q);
y.resize(q);
for (int i = 0; i < q; i++) {
assert(scanf("%d%d", &x[i], &y[i]) == 2);
}
fclose(stdin);
init(k, r);
for (int i = 0; i < q; i++) {
answer[i] = compare_plants(x[i], y[i]);
}
for (int i = 0; i < q; i++) {
printf("%d\n", answer[i]);
}
fclose(stdout);
return 0;
}
#endif // ngu
Compilation message
plants.cpp: In member function 'void IT1::up(int, int, int, int, int, int)':
plants.cpp:32:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In member function 'int IT1::get(int, int, int, int, int)':
plants.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In member function 'void IT2::up(int, int, int, int, int)':
plants.cpp:58:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In member function 'int IT2::get(int, int, int, int, int)':
plants.cpp:67:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
67 | int mid = l + r >> 1;
| ~~^~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:81:8: warning: variable 'calc' set but not used [-Wunused-but-set-variable]
81 | auto calc = [&] () {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
65880 KB |
Output is correct |
| 2 |
Correct |
7 ms |
66392 KB |
Output is correct |
| 3 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
67932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
65884 KB |
Output is correct |
| 2 |
Correct |
8 ms |
65884 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
66140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
65884 KB |
Output is correct |
| 2 |
Correct |
8 ms |
65884 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
66140 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
65884 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
66036 KB |
Output is correct |
| 2 |
Correct |
8 ms |
66140 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
66108 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
66120 KB |
Output is correct |
| 2 |
Correct |
9 ms |
66012 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
67932 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
65880 KB |
Output is correct |
| 2 |
Correct |
7 ms |
66392 KB |
Output is correct |
| 3 |
Correct |
9 ms |
67932 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
67932 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
