#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;
#ifndef WAIMAI
#include "plants.h"
#endif
#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif
#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second
#define lpos pos*2
#define rpos pos*2+1
const int INF = 1e9;
const int SIZE = 2e5 + 5;
int n, k;
int a[SIZE], p[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];
set<int> s;
set<pair<int, int>> d;
int dis(int l, int r) {
return l < r ? r - l : r + n - l;
}
void add(int i) {
if (s.size() == 0) {
s.insert(i);
d.emplace(n, i);
return;
}
auto it = s.lower_bound(i);
int L = (it == s.begin() ? *s.rbegin() : *prev(it));
int R = (it == s.end() ? *s.begin() : *it);
d.erase({dis(L, R), R});
d.emplace(dis(L, i), i);
d.emplace(dis(i, R), R);
s.insert(i);
}
void del(int i) {
if (s.size() == 1) {
s.clear();
d.clear();
return;
}
auto it = s.lower_bound(i);
int L = (it == s.begin() ? *s.rbegin() : *prev(it));
int R = (next(it) == s.end() ? *s.begin() : *next(it));
s.erase(it);
d.erase({dis(L, i), i});
d.erase({dis(i, R), R});
d.emplace(dis(L, R), R);
}
int mn[SIZE * 4], lazy[SIZE * 4];
void push(int pos, int l, int r) {
mn[pos] += lazy[pos];
if (l < r) {
lazy[lpos] += lazy[pos];
lazy[rpos] += lazy[pos];
}
lazy[pos] = 0;
}
void pull(int pos, int l, int r) {
int mid = (l + r) / 2;
push(lpos, l, mid);
push(rpos, mid + 1, r);
mn[pos] = min(mn[lpos], mn[rpos]);
}
void build(int pos, int l, int r) {
if (l == r) {
mn[pos] = k - 1 - a[l];
return;
}
int mid = (l + r) / 2;
build(lpos, l, mid);
build(rpos, mid + 1, r);
mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int L, int R, int x) {
if (l == L && r == R) {
lazy[pos] += x;
return;
}
push(pos, L, R);
int mid = (L + R) / 2;
if (r <= mid) upd(lpos, l, r, L, mid, x);
else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
else {
upd(lpos, l, mid, L, mid, x);
upd(rpos, mid + 1, r, mid + 1, R, x);
}
pull(pos, L, R);
}
void dfs(int pos, int l, int r) {
push(pos, l, r);
if (mn[pos] != 0) return;
if (l == r) {
add(l);
mn[pos] += INF;
return;
}
int mid = (l + r) / 2;
dfs(lpos, l, mid);
dfs(rpos, mid + 1, r);
pull(pos, l, r);
}
int mnp[SIZE * 4];
bool vs[SIZE];
int cmp(int l, int r) {
int mnl = p[l], mnr = p[r];
return (!vs[l] && (vs[r] || mnl < mnr)) ? l : r;
}
void build2(int pos, int l, int r) {
if (l == r) {
mnp[pos] = l;
return;
}
int mid = (l + r) / 2;
build2(lpos, l, mid);
build2(rpos, mid + 1, r);
mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
void upd2(int pos, int l, int r, int p) {
if (l == r) {
vs[l] = 1;
return;
}
int mid = (l + r) / 2;
if (p <= mid) upd2(lpos, l, mid, p);
else upd2(rpos, mid + 1, r, p);
mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
int que(int pos, int l, int r, int L, int R) {
if (l == L && r == R) return mnp[pos];
int mid = (L + R) / 2;
if (r <= mid) return que(lpos, l, r, L, mid);
if (l > mid) return que(rpos, l, r, mid + 1, R);
return cmp(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
}
int que(int l, int r) {
int re = l <= r ? que(1, l, r, 0, n - 1) : cmp(que(1, l, n - 1, 0, n - 1), que(1, 0, r, 0, n - 1));
if (vs[re]) re = -1;
//debug(l, r, re);
return re;
}
const int KSIZ = 2e5;
int id[SIZE], deg[SIZE];
bitset<KSIZ> is[KSIZ];
void init(int _k, vector<int> r) {
n = r.size();
k = _k;
FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
build(1, 0, n - 1);
int sz = n;
FOR (i, 0, n - 1) {
if (sz == 0) break;
dfs(1, 0, n - 1);
vector<int> all;
assert(d.size() > 0);
for (auto it = d.rbegin(); it != d.rend(); it++) {
auto [ld, j] = *it;
if (ld < k) break;
all.pb(j);
}
assert(all.size() > 0);
sz -= all.size();
for (int j : all) {
del(j);
p[j] = i;
int l = j - k + 1, r = j - 1;
if (l < 0) l += n;
if (r < 0) r += n;
if (l <= r) upd(1, l, r, 0, n - 1, -1);
else {
upd(1, l, n - 1, 0, n - 1, -1);
upd(1, 0, r, 0, n - 1, -1);
}
}
}
iota(id, id + n, 0);
sort(id, id + n, [](int l, int r) {
return p[l] < p[r];
});
build2(1, 0, n - 1);
FOR (i, 0, n - 1) {
int cur = id[i];
//debug(cur);
int l = cur - k + 1, r = cur - 1;
if (l < 0) l += n;
if (r < 0) r += n;
int to = que(l, r);
if (to != -1) adj[cur].pb(to), deg[to]++;
l = cur + 1, r = cur + k - 1;
if (l >= n) l -= n;
if (r >= n) r -= n;
to = que(l, r);
if (to != -1) adj[cur].pb(to), deg[to]++;
upd2(1, 0, n - 1, cur);
}
//FOR (i, 0, n - 1) for (int j : adj[i]) debug(i, j);
queue<int> q;
FOR (i, 0, n - 1) if (!deg[i]) q.push(i);
while (q.size()) {
int pos = q.front();
q.pop();
is[pos][pos] = 1;
//debug(pos);
//FOR (i, 0, n - 1) cout << is[pos][i]; cout << '\n';
for (int np : adj[pos]) {
is[np] |= is[pos];
if (--deg[np] == 0) q.push(np);
}
}
}
int compare_plants(int x, int y) {
return is[x][y] ? 1 : is[y][x] ? -1 : 0;
}
/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1
in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0
ex1(4 1 2 5 3 0)
6 4 5
1 3 2 0 1 3
0 1
3 4
2 0
1 3
5 2
*/
/*
if (k == 2) {
FOR (i, 0, n - 1) {
if (a[i] == 1) adj[i].pb((i + 1) % n);
else adj[(i + 1) % n].pb(i);
}
int sz = 0;
FOR (i, 0, n - 1) if (adj[i].size() == 2) {
for (int x : adj[i]) {
int cnt = 0;
g[i].pb(sz, cnt++);
while (adj[x].size()) {
g[x].pb(sz, cnt++);
x = adj[x][0];
}
g[x].pb(sz, cnt++);
sz++;
}
}
return;
}
*/
#ifdef WAIMAI
int main() {
int n, k, q;
vector<int> r;
vector<int> x;
vector<int> y;
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
Compilation message
/tmp/cc4ajdCX.o: in function `void std::__adjust_heap<int*, long, int, __gnu_cxx::__ops::_Iter_comp_iter<init(int, std::vector<int, std::allocator<int> >)::{lambda(int, int)#1}> >(int*, long, int*, int, __gnu_cxx::__ops::_Iter_comp_iter<init(int, std::vector<int, std::allocator<int> >)::{lambda(int, int)#1}>) [clone .constprop.0]':
plants.cpp:(.text+0x33): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0xa1): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/cc4ajdCX.o
/tmp/cc4ajdCX.o: in function `void std::__introsort_loop<int*, long, __gnu_cxx::__ops::_Iter_comp_iter<init(int, std::vector<int, std::allocator<int> >)::{lambda(int, int)#1}> >(int*, __gnu_cxx::__ops::_Iter_comp_iter<init(int, std::vector<int, std::allocator<int> >)::{lambda(int, int)#1}>, long, __gnu_cxx::__ops::_Iter_comp_iter<init(int, std::vector<int, std::allocator<int> >)::{lambda(int, int)#1}>)':
plants.cpp:(.text+0x17a): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/cc4ajdCX.o
/tmp/cc4ajdCX.o: in function `build2(int, int, int) [clone .part.0]':
plants.cpp:(.text+0x634): relocation truncated to fit: R_X86_64_PC32 against symbol `mnp' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0x65b): relocation truncated to fit: R_X86_64_PC32 against symbol `vs' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0x66b): relocation truncated to fit: R_X86_64_PC32 against symbol `p' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0x6b3): relocation truncated to fit: R_X86_64_PC32 against symbol `mnp' defined in .bss section in /tmp/cc4ajdCX.o
/tmp/cc4ajdCX.o: in function `upd(int, int, int, int, int, int) [clone .part.0]':
plants.cpp:(.text+0xa87): relocation truncated to fit: R_X86_64_PC32 against symbol `mn' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0xa90): relocation truncated to fit: R_X86_64_PC32 against symbol `lazy' defined in .bss section in /tmp/cc4ajdCX.o
/tmp/cc4ajdCX.o: in function `upd(int, int, int, int, int, int) [clone .part.0] [clone .constprop.0]':
plants.cpp:(.text+0xcb4): relocation truncated to fit: R_X86_64_PC32 against symbol `lazy' defined in .bss section in /tmp/cc4ajdCX.o
plants.cpp:(.text+0xcbe): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
