Submission #1214075

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214075		hengliao	Comparing Plants (IOI20_plants)	C++20	100 / 100	1436 ms	128900 KiB

plants

#pragma GCC optimize("Ofast")
#include "plants.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef int ll;

namespace{
    const ll mxN=2e5+5; // warning  remember to build
    const ll inf=1e9;
    const ll LOG=21;

    struct segtree{
        vector<array<ll, 3>> tree;
        vector<array<ll, 2>> lazy;
        ll treelen;

        void init(ll siz){
            treelen=siz+1;
            while(__builtin_popcount(treelen)!=1) treelen++;
            tree=vector<array<ll, 3>> (2*treelen, {0, 0, 0});
            lazy=vector<array<ll, 2>> (2*treelen, {0, 0});
        }

        void build(ll idx, ll low, ll high){
            if(low==high) return;
            ll mid=(low+high)/2;
            build(2*idx, low, mid);
            build(2*idx+1, mid+1, high);
            tree[idx]=min(tree[2*idx], tree[2*idx+1]);
        }

        void push(ll idx, ll low, ll high){
            for(ll i=2*idx;i<=2*idx+1;i++){
                for(ll j=0;j<2;j++){
                    tree[i][j]+=lazy[idx][j];
                    lazy[i][j]+=lazy[idx][j];
                }
            }
            lazy[idx][0]=0;
            lazy[idx][1]=0;
        }

        void update1(ll idx, ll low, ll high, ll qlow, ll qhigh, ll id, ll val){
            if(low>=qlow && high<=qhigh){
                tree[idx][id]+=val;
                lazy[idx][id]+=val;
                return;
            }
            if(low>qhigh || high<qlow) return;
            push(idx, low, high);
            ll mid=(low+high)/2;
            update1(2*idx, low, mid, qlow, qhigh, id, val);
            update1(2*idx+1, mid+1, high, qlow, qhigh, id, val);
            tree[idx]=min(tree[2*idx], tree[2*idx+1]);
        }

        void update(ll qlow, ll qhigh, ll id, ll val){
            update1(1, 0, treelen-1, qlow, qhigh, id, val);
        }

        array<ll, 3> getmin1(ll idx, ll low, ll high, ll qlow, ll qhigh){
            if(low>=qlow && high<=qhigh){
                return tree[idx];
            }
            if(low>qhigh || high<qlow) return {inf, inf, inf};
            push(idx, low, high);
            ll mid=(low+high)/2;
            return min(getmin1(2*idx, low, mid, qlow, qhigh),
            getmin1(2*idx+1, mid+1, high, qlow, qhigh));
        }

        array<ll, 3> getmin(ll qlow, ll qhigh){
            return getmin1(1, 0, treelen-1, qlow, qhigh);
        }

        ll bssmall(ll idx, ll low, ll high){
            if(low==high) return low;
            ll mid=(low+high)/2;
            push(idx, low, high);
            if(tree[2*idx][0]<=0){
                return bssmall(2*idx, low, mid);
            }
            else{
                return bssmall(2*idx+1, mid+1, high);
            }
        }

        ll bsbig(ll idx, ll low, ll high, ll qlow, ll qhigh){
            if(tree[idx][0]>0) return inf;
            if(low>=qlow && high<=qhigh){
                return bssmall(idx, low, high);
            }
            if(low>qhigh || high<qlow) return inf;
            push(idx, low, high);
            ll mid=(low+high)/2;
            ll re=bsbig(2*idx, low, mid, qlow, qhigh);
            if(re!=inf){
                return re;
            }
            return bsbig(2*idx+1, mid+1, high, qlow, qhigh);
        }

        ll bs(ll qlow, ll qhigh){
            return bsbig(1, 0, treelen-1, qlow, qhigh);
        }
        
    };

    ll n, k;
    vll adj[mxN];
    // ll ans[mxN][mxN];
    bool done[mxN];
    ll val[2*mxN];
    bool visited[mxN];
    array<ll, 3> up[mxN][LOG], up2[mxN][LOG];
    segtree seg;

    void dfs(ll cur){
        if(visited[cur]) return;
        visited[cur]=1;
        for(auto &it:adj[cur]){
            dfs(it);
        }
    }
}

void init(int K, vector<int> a) {
    n=a.size();
    k=K;
    seg.init(n);

    for(ll i=0;i<n;i++){
        seg.tree[i+seg.treelen]={a[i], 0, i};
    }

    seg.build(1, 0, seg.treelen-1);

    auto add=[&](ll idx){
        ll lef=(idx+1)%n;
        ll rig=(idx+k-1)%n;
        if(lef>rig){
            seg.update(lef, n-1, 1, 1);
            seg.update(0, rig, 1, 1); 
        }    
        else{
            seg.update(lef, rig, 1, 1);
        }
    };

    for(ll i=0;i<n;i++){
        if(a[i]==0){
            add(i);
        }
    }
        
    for(ll i=n-1;i>=0;i--){
        ll dumb=0;
        array<ll, 3> tep=seg.getmin(0, n-1);
        dumb=tep[2];
            
        val[dumb]=i;
        val[dumb+n]=i;
        seg.update(dumb, dumb, 0, inf);
        ll lef=(dumb+1)%n;
        ll rig=(dumb+k-1)%n;
        if(lef>rig){
            seg.update(lef, n-1, 1, -1);
            seg.update(0, rig, 1, -1); 
        }    
        else{
            seg.update(lef, rig, 1, -1);
        }
        lef=(dumb-k+1+n)%n;
        rig=(dumb-1+n)%n;
        if(lef>rig){
            seg.update(lef, n-1, 0, -1);
            seg.update(0, rig, 0, -1); 
            
            ll pre=lef;
                
            while(pre<=n-1){
                ll good=seg.bs(pre, n-1);
                if(good==inf) break;
                add(good);
                pre=good+1;
            }

            pre=0;

            while(pre<=rig){

                ll good=seg.bs(pre, rig);
                if(good==inf) break;
                add(good);
                pre=good+1;
            }
        }    
        else{
            seg.update(lef, rig, 0, -1);
            ll pre=lef;

            while(pre<=rig){
                ll good=seg.bs(pre, rig);
                if(good==inf) break;
                add(good);
                pre=good+1;
            }
        }
            
    }
        
    set<pll> st;
    for(ll i=n-k+1;i<=n-1;i++){
        st.insert({val[i], i});
    }
    for(ll i=0;i<n;i++){
        auto it=st.lower_bound({val[i], i});
        if(it==st.begin()){
            up[i][0]={i, val[i], 0};
        }
        else{
            pll tep=*prev(it);
            ll nxt=tep.S;
            up[i][0]={nxt, val[nxt], 0};
            if(nxt>i){
                up[i][0][2]++;
            }
        }
        ll pid=(i-k+1+n)%n;
        st.erase({val[pid], pid});
        st.insert({val[i], i});
    }
    st.clear();
    for(ll i=0;i<k-1;i++){
        st.insert({val[i], i});
    }
    for(ll i=n-1;i>=0;i--){
        auto it=st.lower_bound({val[i], i});
        if(it==st.begin()){
            up2[i][0]={i, val[i], 0};
        }
        else{
            pll tep=*prev(it);
            ll nxt=tep.S;
            up2[i][0]={nxt, val[nxt], 0};
            if(nxt<i){
                up2[i][0][2]++;
            }
        }
        ll pid=(i+k-1)%n;
        st.erase({val[pid], pid});
        st.insert({val[i], i});
    }
    for(ll j=1;j<LOG;j++){
        for(ll i=0;i<n;i++){
            ll nxt=up[i][j-1][0];
            up[i][j][0]=up[nxt][j-1][0];
            up[i][j][1]=up[nxt][j-1][1];
            up[i][j][2]=up[i][j-1][2]+up[nxt][j-1][2];
        }
    }
    for(ll j=1;j<LOG;j++){
        for(ll i=0;i<n;i++){
            ll nxt=up2[i][j-1][0];
            up2[i][j][0]=up2[nxt][j-1][0];
            up2[i][j][1]=up2[nxt][j-1][1];
            up2[i][j][2]=up2[i][j-1][2]+up2[nxt][j-1][2];
        }
    }
}

int compare_plants(int x, int y) {
    // if(2*k>n){

    auto bsl=[&](ll cur, ll e){
        ll sum=0;
        for(ll i=LOG-1;i>=0;i--){
            if(up[cur][i][1]>=e){
                sum+=up[cur][i][2];
                cur=up[cur][i][0];
            }
        }
        array<ll, 2> re={cur, sum};
        return re;
    };

    auto bsr=[&](ll cur, ll e){
        ll sum=0;
        for(ll i=LOG-1;i>=0;i--){
            if(up2[cur][i][1]>=e){
                sum+=up2[cur][i][2];
                cur=up2[cur][i][0];
            }
        }
        array<ll, 2> re={cur, sum};
        return re;
    };

    if(val[x]>val[y]){
        array<ll, 2> re=bsl(x, val[y]);
        ll dumb=0;
        if(y>x) dumb++;
        if(re[1]>dumb){
            return 1;
        }
        else if(re[1]==dumb && re[0]<=y){
            return 1;
        }
        re=bsr(x, val[y]);
        dumb=0;
        if(y<x) dumb++;
        if(re[1]>dumb){
            return 1;
        }
        else if(re[1]==dumb && re[0]>=y){
            return 1;
        }
        return 0;
    }
    else{
        array<ll, 2> re=bsl(y, val[x]);
        ll dumb=0;
        if(x>y) dumb++;
        if(re[1]>dumb){
            return -1;
        }
        else if(re[1]==dumb && re[0]<=x){
            return -1;
        }
        re=bsr(y, val[x]);
        dumb=0;
        if(x<y) dumb++;
        if(re[1]>dumb){
            return -1;
        }
        else if(re[1]==dumb && re[0]>=x){
            return -1;
        }
        return 0; 
    }
    
    // }
    // return (int) ans[x][y];
}

• 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