#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];
bool can[5010][5010];
void dfs(int v,int root){
can[root][v]=true;
for (int to:g[v]){
if (!can[root][to]){
dfs(to,root);
}
}
}
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);
if (nxt1==-1) nxt1=pos;
go1[pos]=nxt1;
int nxt2=get_pos(n,(pos-k+1+n)%n,pos);
if (nxt2==-1) nxt2=pos;
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;
}
}
for (int i=0;i<1;i++){
dfs(i,i);
}
return;
}
int compare_plants(int x, int y) {
if (can[x][y]) return 1;
if (can[y][x]) return -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 2 2
0 1 0 1
0 3
1 3
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 2 |
Correct |
5 ms |
7424 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7424 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
