//#define SYS
#ifdef SYS
#include "plants.h"
#endif // SYS
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=300010;
struct node{
int mx,l,r,best;
};
node t[N*4];
int w[N*4];
int a[N];
int p[N];
int nn,kk;
node Merge(node A,node B){
if (A.mx>B.mx) {
return A;
}
if (A.mx<B.mx) {
return B;
}
node C;
C.mx=A.mx;
C.l=A.l;
C.r=B.r;
if (A.best!=-1) C.best=A.best;
else if (B.best!=-1) C.best=B.best;
else if (B.l>=A.r+kk) C.best=B.l;
else C.best=-1;
return C;
}
void build(int v,int l,int r){
if (l>r) return;
w[v]=0;
t[v].best=-1;
if (l==r){
t[v].mx=a[l];
t[v].l=t[v].r=l;
t[v].best=-1;
return;
}
int m=(l+r)/2;
build(v+v,l,m);
build(v+v+1,m+1,r);
t[v]=Merge(t[v+v],t[v+v+1]);
}
void push(int v){
t[v+v].mx+=w[v];
t[v+v+1].mx+=w[v];
w[v+v]+=w[v];
w[v+v+1]+=w[v];
w[v]=0;
}
void upd(int v,int l,int r,int L,int R,int x){
if (l>R || r<L) return;
if (l>=L && r<=R){
t[v].mx+=x;
w[v]+=x;
return;
}
push(v);
int m=(l+r)/2;
upd(v+v,l,m,L,R,x);
upd(v+v+1,m+1,r,L,R,x);
t[v]=Merge(t[v+v],t[v+v+1]);
}
void add(int n,int l,int r,int x){
if (l<=r){
upd(1,0,n-1,l,r,x);
} else {
upd(1,0,n-1,l,n-1,x);
upd(1,0,n-1,0,r,x);
}
}
int go1[N];
int go2[N];
int rp[N];
pair<int,int>t1[N*4];
void upd1(int v,int l,int r,int pos,int x){
if (l==r){
t1[v]={x,l};
return;
}
int m=(l+r)/2;
if (pos<=m) upd1(v+v,l,m,pos,x);
else upd1(v+v+1,m+1,r,pos,x);
t1[v]=max(t1[v+v],t1[v+v+1]);
}
pair<int,int> get1(int v,int l,int r,int L,int R){
if (l>R || r<L) return {-1,-1};
if (l>=L && r<=R) return t1[v];
int m=(l+r)/2;
return max(get1(v+v,l,m,L,R),get1(v+v+1,m+1,r,L,R));
}
int get_pos(int n,int l,int r){
pair<int,int>cur;
if (l<=r){
cur=get1(1,0,n-1,l,r);
} else {
cur=max(get1(1,0,n-1,0,r),get1(1,0,n-1,l,n-1));
}
if (cur.first<=0) return -1;
return cur.second;
}
vector<int>g[N];
vector<int>rg[N];
int go_1(int x){
if (go1[x]==x) return x;
return go1[x]=go_1(go1[x]);
}
int go_2(int x){
if (go2[x]==x) return x;
return go2[x]=go_2(go2[x]);
}
bool used[N];
void dfs(int v){
used[v]=true;
for (int to:g[v]){
if (!used[to]) dfs(to);
}
}
bool used1[N];
void dfs1(int v){
used1[v]=true;
for (int to:rg[v]){
if (!used1[to]) dfs1(to);
}
}
const int L=20;
int up1[N][L];
int up2[N][L];
bool can1(int x,int y){
if (p[x]<p[y]) return 0;
// cout<<x<<" "<<y<<endl;
int last=x;
for (int i=L-1;i>=0;i--){
if (p[up1[x][i]]>=p[y]) x=up1[x][i];
}
// cout<<x<<" "<<y<<endl<<endl;
if (last<y){
return (x>=y || x<last);
} else {
return (x>=y && x<last);
}
}
bool can2(int x,int y){
if (p[x]<p[y]) return 0;
int last=x;
for (int i=L-1;i>=0;i--){
if (p[up2[x][i]]>=p[y]) x=up2[x][i];
}
if (last>y){
return (x<=y || x>last);
} else {
return (x<=y && x>last);
}
}
bool can(int x,int y){
return (can1(x,y)|can2(x,y));
}
void init(int k, std::vector<int> r) {
int n=r.size();
nn=n;
kk=k;
for (int &i:r){
i=k-i-1;
}
for (int i=0;i<n;i++) a[i]=r[i];
build(1,0,n-1);
for (int cur=n;cur>=1;cur--){
if (t[1].mx>k-1) exit(1);
int pos=(t[1].best==-1 ? t[1].l : t[1].best);
p[pos]=cur;
rp[cur]=pos;
// cout<<pos<<endl;
add(n,(pos-k+1+n)%n,pos,1);
add(n,pos,pos,-n*3);
}
for (int cur=1;cur<=n;cur++){
int pos=rp[cur];
int nxt1=get_pos(n,pos,(pos+k-1)%n);
int nxt2=get_pos(n,(pos-k+1+n)%n,pos);
if (nxt1!=-1) g[pos].push_back(nxt1),rg[nxt1].push_back(pos);
else nxt1=pos;
if (nxt2!=-1) g[pos].push_back(nxt2),rg[nxt2].push_back(pos);
else nxt2=pos;
go1[pos]=nxt1;
go2[pos]=nxt2;
upd1(1,0,n-1,pos,cur);
if (nxt1!=pos) {
g[pos].push_back(nxt1);
// cout<<pos<<" "<<nxt1<<endl;
}
if (nxt2!=pos) {
g[pos].push_back(nxt2);
// cout<<pos<<" "<<nxt2<<endl;
}
up1[pos][0]=go1[pos];
up2[pos][0]=go2[pos];
}
// for (int i=0;i<n;i++){
// cout<<i<<" "<<go1[i]<<" "<<go2[i]<<" "<<p[i]<<endl;
// }
for (int i=1;i<L;i++){
for (int j=0;j<n;j++){
up1[j][i]=up1[up1[j][i-1]][i-1];
up2[j][i]=up2[up2[j][i-1]][i-1];
}
}
return;
}
int compare_plants(int x, int y) {
if (can(x,y)) return 1;
if (can(y,x)) return -1;
exit(1);
return 0;
}
#ifndef SYS
#include <cstdio>
#include <cassert>
#include <vector>
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;
int main() {
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
/*
4 3 2
0 1 1 2
0 2
1 2
*/
Compilation message
/tmp/ccCTv8D3.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc2rsEmd.o:plants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
