Submission #622711

#	Time	Username	Problem	Language	Result	Execution time	Memory
622711		leaked	Comparing Plants (IOI20_plants)	C++17	27 / 100	706 ms	46208 KiB

plants

#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

const int N=2e5+1;

struct segtree{
    pii t[4*N];
    int p[4*N];
    vec<int> a;

    void push(int v,int tl,int tr){
        for(auto &u : {v<<1,v<<1|1}){
            t[u].f+=p[v];
            p[u]+=p[v];
        }
        p[v]=0;
    }

    void build(int v,int tl,int tr){
        p[v]=0;
        if(tl==tr){
            t[v]={a[tl],tl};
        }
        else{
            int tm=(tl+tr)>>1;
            build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
            t[v]=min(t[v<<1],t[v<<1|1]);
        }
    }

    void add(int l,int r,int x,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            t[v].f+=x;p[v]+=x;
//            cout<<tl<<' '<<tr<<' '<<x<<endl;
            return;
        }
        if(tl>r||tr<l) return;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        add(l,r,x,v<<1,tl,tm);add(l,r,x,v<<1|1,tm+1,tr);
        t[v]=min(t[v<<1],t[v<<1|1]);
    }
    pii get(int l,int r,int v,int tl,int tr){
        if(tl>=l&&tr<=r) return t[v];
        if(tl>r||tr<l) return m_p(1e9,-1);
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return min(get(l,r,v<<1,tl,tm),get(l,r,v<<1|1,tm+1,tr));
    }
}sega;

int n,k;

int h[N],it=0;

int _find(int i){
    pii c;
    if((i-k+1)<0){
        int r=k-(i+1);
        c=sega.get(n-r,n-1,1,0,n-1);
        if(c.f>0){
            c=sega.get(0,i-1,1,0,n-1);
        }
    }
    else{
        c=sega.get(i-k+1,i-1,1,0,n-1);
    }
    return (c.f<=0?c.s:-1);
}

int ht[N];

void place(int i){
    sega.add(i,i,1e9,1,0,n-1);
    int j=_find(i);
//    cout<<"PLACE "<<i<<endl;
    while(j!=-1){
        place(j);
        j=_find(i);
    }
    ht[i]=it++;

    if((i-k+1)<0){
        int r=k-(i+1);
        sega.add(n-r,n-1,-1,1,0,n-1);
        sega.add(0,i,-1,1,0,n-1);
    }
    else{
        sega.add(i-k+1,i,-1,1,0,n-1);
    }
}


int lft[N][20],rgt[N][20];


void init(int k, std::vector<int> r){
    n=sz(r);::k=k;
    sega.a=r;
    sega.build(1,0,n-1);
    fill(ht,ht+n,-1);
    while(1){
        pii c=sega.t[1];
        if(c.f>0){
            break;
        }
        int j=c.s;
        place(j);
    }

    for(int i=0;i<n;i++) ht[i]=n-ht[i]+1;

    vec<int> ids(n);
    sort(all(ids),[&](int i,int j){return ht[i]<ht[j];});

    const int inf=(int)(1e9)-1;

    for(int i=0;i<n;i++) sega.a[i]=inf;

    sega.build(1,0,n-1);

    for(auto &i : ids){
        pii c=((i+1)>=k?sega.get(i-k+1,i-1,1,0,n-1):min(sega.get(0,i-1,1,0,n-1),sega.get(n-(k-(i+1)),n-1,1,0,n-1)));

        if(c.f>=inf) lft[i][0]=0;
        else lft[i][0]=(i+n-c.s)%n;

        c=(i+k-1<n?sega.get(i+1,i+k-1,1,0,n-1):min(sega.get(i+1,n-1,1,0,n-1),sega.get(0,k-(n-i)-1,1,0,n-1)));
        if(c.f>=inf) rgt[i][0]=0;
        else rgt[i][0]=(c.s-i+n)%n;

        sega.add(i,i,-inf-ht[i],1,0,n-1);
    }

    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            lft[j][i]=lft[j][i]+lft[(j+n-lft[j][i])%n][i];
            rgt[j][i]=rgt[j][i]+rgt[(j+rgt[j][i])%n][i];
            if(lft[j][i]>n) lft[j][i]=0;
            if(rgt[j][i]>n) rgt[j][i]=0;
        }
    }
}
int compare_plants(int x, int y){
    int z=x;
    for(int i=19;i>=0;i--){
        if(rgt[z][i]<(y-z+n)%n)
            z=(z+rgt[z][i])%n;
    }
    if(ht[z]>ht[y] && (y-z+n)%n<k) return 1;

    z=y;
    for(int i=19;i>=0;i--){
        if(rgt[z][i]<(x-z+n)%n)
            z=(z+rgt[z][i])%n;
    }
    if(ht[z]>ht[x] && (x-z+n)%n<k) return -1;

    z=y;
    for(int i=19;i>=0;i--){
        if(lft[z][i]<(z-x+n)%n)
            z=(z-lft[z][i]+n)%n;
    }
    if(ht[z]>ht[x] && (z-x+n)%n<k) return -1;

    z=x;

    for(int i=19;i>=0;i--){
        if(lft[z][i]<(z-y+n)%n)
            z=(z-lft[z][i]+n)%n;
    }

    if(ht[z]>ht[y] && (z-y+n)%n<k) return 1;

    return 0;
}

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