oj.uz

Submission #304657

# Submission time Handle Problem Language Result Execution time Memory
304657 2020-09-21T16:54:08 Z oleh1421 Comparing Plants (IOI20_plants) C++17
0 / 100
 90 ms 26872 KB 
#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 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);
    }
}
bool can1[5010][5010];
void dfs1(int v,int root){
    can1[root][v]=true;
    for (int to:rg[v]){
        if (!can1[root][to]) dfs1(to,root);
    }
}
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 {
////        last>y<=x
//        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);
        for (int i=1;i<k;i++){
            int nxt=(cur+i)%n;
            if (p[nxt]<p[pos]){
                g[pos].push_back(nxt);
            }
        }
        for (int i=1;i<k;i++){
            int nxt=(cur-i+n)%n;
            if (p[nxt]<p[pos]){
                g[pos].push_back(nxt);
            }
        }

//        if (nxt1!=-1) g[pos].push_back(nxt1);
//        else nxt1=pos;
//        if (nxt2!=-1) rg[pos].push_back(nxt2);
//        else nxt2=pos;
//        go1[pos]=nxt1;
//        go2[pos]=nxt2;
//        upd1(1,0,n-1,pos,cur);
//
//        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];
        }
    }
    for (int i=0;i<n;i++){
        dfs(i,i);
//        dfs1(i,i);
    }

	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

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:192:13: warning: unused variable 'nxt1' [-Wunused-variable]
  192 |         int nxt1=get_pos(n,pos,(pos+k-1)%n);
      |             ^~~~
plants.cpp:193:13: warning: unused variable 'nxt2' [-Wunused-variable]
  193 |         int nxt2=get_pos(n,(pos-k+1+n)%n,pos);
      |             ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Incorrect 9 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14504 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Incorrect 9 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14504 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Incorrect 9 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 9 ms 14592 KB Output is correct
3 Incorrect 90 ms 26872 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 14464 KB Output is correct
2 Correct 10 ms 14464 KB Output is correct
3 Incorrect 9 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Incorrect 10 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14464 KB Output is correct
2 Correct 9 ms 14464 KB Output is correct
3 Incorrect 9 ms 14464 KB Output isn't correct
4 Halted 0 ms 0 KB -