Submission #304682

#	Time	Username	Problem	Language	Result	Execution time	Memory
304682		oleh1421	Comparing Plants (IOI20_plants)	C++17	100 / 100	2023 ms	171640 KiB

plants

#define SYS
#ifdef SYS
#include "plants.h"
#endif // SYS


#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=400010;
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=25;
int up1[N][L];
ll skip1[N][L];
int up2[N][L];
ll skip2[N][L];
bool can1(int x,int y){
    if (p[x]<p[y]) return 0;
//    cout<<x<<" "<<y<<endl;
    int last=x;
    ll skip=0;
    for (int i=L-1;i>=0;i--){
        if (p[up1[x][i]]>=p[y]) skip+=skip1[x][i],x=up1[x][i];
    }
    if (skip>=nn) return 1;
//    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;
    ll skip=0;
    for (int i=L-1;i>=0;i--){
        if (p[up2[x][i]]>=p[y]) skip+=skip2[x][i],x=up2[x][i];
    }
    if (skip>=nn) return 1;
    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);
        skip1[pos][0]=(go1[pos]-pos+n)%n;
        up1[pos][0]=go1[pos];
        skip2[pos][0]=(pos-go2[pos]+n)%n;
        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++){
            skip1[j][i]=skip1[j][i-1]+skip1[up1[j][i-1]][i-1];
            up1[j][i]=up1[up1[j][i-1]][i-1];
            skip2[j][i]=skip2[j][i-1]+skip2[up2[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



*/

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25