#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end();
#define p(x) cerr<<#x<<" = "<<x<<endl;
#define p2(x,y) cerr<<#x<<","<<#y<<" = "<<"("<<x<<"-"<<y<<")"<<endl;
#define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
vector<int> arr,bigger;
vector<int> seg;
vector<int> laz;
vector<int> pou;
void join(int par, int x, int y){
if(seg[x]<seg[y]){
seg[par] = seg[x];
pou[par] = pou[x];
}
else{
seg[par] = seg[y];
pou[par] = pou[y];
}
}
void push(int par, int x, int y){
seg[x] += laz[par];
laz[x] += laz[par];
seg[y] += laz[par];
laz[y] += laz[par];
laz[par] = 0;
}
void build(int s, int e, int idx){
if(s==e){
seg[s] = 1e9;
pou[s] = s;
return;
}
int mid = (s+e)/2;
build(s,mid,idx*2);
build(mid+1,e,idx*2+1);
join(idx,idx*2,idx*2+1);
}
void update(int s, int e, int idx, int qs, int qe, int x){
if(qs<=s && e<=qe){
seg[idx] += x;
laz[idx] += x;
return;
}
if(s>qe || e<qs)return;
int mid = (s+e)/2;
push(idx,idx*2,idx*2+1);
update(s,mid,idx*2,qs,qe,x);
update(mid+1,e,idx*2+1,qs,qe,x);
join(idx,idx*2,idx*2+1);
}
void init(int k, vector<int> r) {
int n = r.size();
arr.assign(n,0);
bigger.assign(n,0);
seg.assign((n+5)*4,0);
laz.assign((n+5)*4,0);
pou.assign((n+5)*4,0);
int i,j;
build(0,n-1,1);
for(i=0;i<n;i++){
if(r[i]==0){
if(i+1<n){
update(0,n-1,1,i+1,min(n-1,i+k-1),1);
}
if(i+k-1>=n){
update(0,n-1,1,0,(i+k-1)%n,1);
}
update(0,n-1,1,i,i,-1e9);
}
}
int curr = n;
for(int t=0;t<n;t++){
int x = pou[0];
arr[x] = curr--;
update(0,n-1,1,x,x,1e9);
//pv(arr)
//for(auto xx : s)
// cout<<xx.pos<<" ";
//cout<<endl;
//pv(bigger)
//pv(r)
//cout<<endl;
if(x+1<n){
update(0,n-1,1,x+1,min(n-1,x+k-1),-1);
}
if(x+k-1>=n){
update(0,n-1,1,0,(x+k-1)%n,-1);
}
for(j=1;j<k;j++){
//cout<<j<<" "<<k<<endl;
int idx = x-j;
if(idx<0)idx+=n;
if(r[idx]>0){
r[idx]--;
if(r[idx]==0){
if(idx+1<n){
update(0,n-1,1,idx+1,min(n-1,idx+k-1),1);
}
if(idx+k-1>=n){
update(0,n-1,1,0,(idx+k-1)%n,1);
}
update(0,n-1,1,idx,idx,-1e9);
}
}
}
//pv(bigger)
//pv(zer)
//pv(r)
}
pv(arr)
}
int compare_plants(int x, int y) {
if(arr[x]>arr[y])return 1;
return -1;
}
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;
}
Compilation message
/tmp/cc6hPER9.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccUZ41gg.o:plants.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
