Submission #893647

#	Time	Username	Problem	Language	Result	Execution time	Memory
893647		abcvuitunggio	Comparing Plants (IOI20_plants)	C++17	0 / 100	120 ms	22080 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct T{
    int mn,pos;
}st[800001];
T operator +(T a, T b){
    return (a.mn>b.mn?b:a);
}
int n,k,lazy[800001],p[200001],id,l[200001][20],r[200001][20],dl[200001][20],dr[200001][20],pos[200001];
vector <int> a;
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].mn+=lazy[node];
    st[node<<1|1].mn+=lazy[node];
    lazy[node<<1]+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={a[l],l};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v)
        return;
    if (l>=u&&r<=v){
        st[node].mn+=val;
        lazy[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=st[node<<1]+st[node<<1|1];
}
T get(int node, int l, int r, int u, int v){
    if (l>v||r<u||u>v)
        return {INF,0};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
T calc(int j){
    if (j<k)
        return get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1);
    else
        return get(1,0,n-1,j-k+1,j-1);
}
void dfs(int i){
    while (!calc(i).mn)
        dfs(calc(i).pos);
    p[i]=id;
    id--;
    if (i<k){
        update(1,0,n-1,0,i-1,-1);
        update(1,0,n-1,n+i-k+1,n-1,-1);
    }
    else
        update(1,0,n-1,i-k+1,i-1,-1);
    update(1,0,n-1,i,i,INF);
}
void init(int K, vector <int> R){
    k=K;
    a=R;
    n=id=a.size();
    build(1,0,n-1);
    while (!st[1].mn)
        dfs(st[1].pos);
    for (int i=0;i<n;i++){
        a[i]=-p[i];
        pos[p[i]]=i;
    }
    build(1,0,n-1);
    for (int j=n;j;j--){
        int i=pos[j];
        update(1,0,n-1,i,i,INF);
        l[i][0]=(calc(i).mn>0?i:calc(i).pos);
        dl[i][0]=(i-l[i][0]+n)%n;
        r[i][0]=(calc(i+k).mn>0?i:calc(i+k).pos);
        dr[i][0]=(r[i][0]-i+n)%n;
    }
    for (int j=1;j<20;j++)
        for (int i=0;i<n;i++){
            l[i][j]=l[l[i][j-1]][j-1];
            dl[i][j]=min(dl[i][j-1]+dl[l[i][j-1]][j-1],INF);
            r[i][j]=r[r[i][j-1]][j-1];
            dr[i][j]=min(dr[i][j-1]+dr[r[i][j-1]][j-1],INF);
        }
}
int check(int x, int y){
    int z=x,dist=(x-y+n)%n;
    for (int i=19;i>=0;i--)
        if (dl[z][i]<dist){
            dist-=dl[z][i];
            z=l[z][i];
        }
    if (dl[z][0]>=dist&&p[z]>p[y])
        return 1;
    z=x,dist=(y-x+n)%n;
    for (int i=19;i>=0;i--)
        if (dr[z][i]<dist){
            dist-=dr[z][i];
            z=r[z][i];
        }
    return (dr[z][0]>=dist&&p[z]>p[y]);
}
int compare_plants(int x, int y){
	return (check(x,y)?1:(check(y,x)?-1:0));
}

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