Submission #1213739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213739		hengliao	Comparing Plants (IOI20_plants)	C++20	44 / 100	3894 ms	20288 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;

    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 n, k;
    vll adj[mxN];
    // ll ans[mxN][mxN];
    bool done[mxN];
    ll val[mxN];
    bool visited[mxN];
    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) {
	memset(done, 0, sizeof(done));
    // memset(ans, 0, sizeof(ans));
    n=a.size();
    k=K;



    // if(2*k>n){

        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--){
            // vll tep;
            // for(ll j=0;j<n;j++){
            //     if(!done[j] && a[j]==0){
            //         tep.pb(j);
            //     }
            // }
            ll dumb=0;
            array<ll, 3> tep=seg.getmin(0, n-1);
            dumb=tep[2];
            // assert(tep[0]==0);
            // assert(tep[1]==0);
            // if((ll) tep.size()==1){
            //     dumb=tep[0];
            // }
            // else{
            //     for(ll j=0;j<(ll) tep.size();j++){
            //         ll pre=(j-1+(ll) tep.size())%((ll) tep.size());
            //         if(((tep[j]-tep[pre]+n)%n)>=k){
            //             dumb=tep[j];
            //             break;
            //         }
            //     }
            // }
            
            val[dumb]=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(true){
                    ll l=pre, r=n-1;
                    ll good=-1;
                    while(l<=r){
                        ll mid=(l+r)/2;
                        array<ll, 3> pooh=seg.getmin(pre, mid);
                        if(pooh[0]==0){
                            good=mid;
                            r=mid-1;
                        }
                        else{
                            l=mid+1;
                        }
                    }
                    if(good==-1) break;
                    add(good);
                    pre=good+1;
                }

                pre=0;

                while(true){
                    ll l=pre, r=rig;
                    ll good=-1;
                    while(l<=r){
                        ll mid=(l+r)/2;
                        array<ll, 3> pooh=seg.getmin(pre, mid);
                        if(pooh[0]==0){
                            good=mid;
                            r=mid-1;
                        }
                        else{
                            l=mid+1;
                        }
                    }
                    if(good==-1) break;
                    add(good);
                    pre=good+1;
                }
            }    
            else{
                seg.update(lef, rig, 0, -1);
                ll pre=lef;

                while(true){
                    ll l=pre, r=rig;
                    ll good=-1;
                    while(l<=r){
                        ll mid=(l+r)/2;
                        array<ll, 3> pooh=seg.getmin(pre, mid);
                        if(pooh[0]==0){
                            good=mid;
                            r=mid-1;
                        }
                        else{
                            l=mid+1;
                        }
                    }
                    if(good==-1) break;
                    add(good);
                    pre=good+1;
                }
            }
            
        }
        return;
        // for(ll i=0;i<n;i++){
        //     cout<<val[i]<<' ';
        // }
        // cout<<'\n';
    // }
    // auto check=[&](ll tar){
    //     if(a[tar]>0) return false;
    //     if(done[tar]) return false;
    //     ll cur=tar;
    //     for(ll i=0;i<k-1;i++){
    //         cur--;
    //         if(cur<0) cur+=n;
    //         if(done[cur]) continue;
    //         if(a[cur]==0) return false;
    //     }
    //     return true;
    // };
    // for(ll rep=0;rep<n;rep++){
    //     ll cur=-1;
    //     for(ll tar=0;tar<n;tar++){
    //         if(check(tar)){
    //             cur=tar;
    //             break;
    //         }
    //     }
    //     done[cur]=1;
    //     for(ll i=1;i<k;i++){
    //         ll cur2=(cur+i)%n;
    //         if(done[cur2]) continue;
    //         adj[cur].pb(cur2);
    //     }
    //     for(ll i=1;i<k;i++){
    //         ll cur2=(cur-i+n)%n;
    //         if(done[cur2]) continue;
    //         a[cur2]--;
    //         adj[cur].pb(cur2);
    //     }
    // }
    // for(ll i=0;i<n;i++){
    //     memset(visited, 0, sizeof(visited));
    //     dfs(i);
    //     for(ll j=0;j<n;j++){
    //         if(visited[j]){
    //             ans[i][j]=1;
    //             ans[j][i]=-1;
    //         }
    //     }
    // }
}

int compare_plants(int x, int y) {
	// if(2*k>n){
        if(val[x]>val[y]) return 1;
        return -1;
    // }
    // return (int) ans[x][y];
}

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