Submission #1178993

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178993		guagua0407	식물 비교 (IOI20_plants)	C++20	0 / 100	1 ms	328 KiB

plants

#include "plants.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    const int inf=1e9;
    int n;
    struct segtree{
        vector<pair<int,int>> st;
        vector<int> lz;
        segtree(int _n){
            n=_n;
            st=vector<pair<int,int>>(n*4);
            lz=vector<int>(n*4);
        }
        void init(int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v]={0,l};
                return;
            }
            int mid=(l+r)/2;
            init(l,mid,v*2);
            init(mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        void push(int v){
            st[v*2].f+=lz[v];
            lz[v*2]+=lz[v];
            st[v*2+1].f+=lz[v];
            lz[v*2+1]+=lz[v];
            lz[v]=0;
        }
        void update(int tl,int tr,int val,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return;
            }
            if(tl<=l and r<=tr){
                st[v].f+=val;
                lz[v]+=val;
                return;
            }
            push(v);
            int mid=(l+r)/2;
            update(tl,min(mid,tr),val,l,mid,v*2);
            update(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
            st[v]=min(st[v*2],st[v*2+1]);
        }
        pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return {inf,-1};
            }
            if(tl<=l and r<=tr){
                return st[v];
            }
            push(v);
            int mid=(l+r)/2;
            return min(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
        }
        void add(int l,int r,int val){
            if(r<0){
                l+=n;
                r+=n;
            }
            if(l>=n){
                l-=n;
                r-=n;
            }
            if(l<0){
                l+=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else if(r>=n){
                r-=n;
                update(l,n-1,val);
                update(0,r,val);
            }
            else{
                update(l,r,val);
            }
        }
    };
    struct segtree2{
        vector<pair<int,int>> st;
        segtree2(int _n){
            n=_n;
            st=vector<pair<int,int>>(n*4);
        }
        void init(int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v]={0,l};
                return;
            }
            int mid=(l+r)/2;
            init(l,mid,v*2);
            init(mid+1,r,v*2+1);
            st[v]=max(st[v*2],st[v*2+1]);
        }
        void update(int pos,int val,int l=0,int r=n-1,int v=1){
            if(l==r){
                st[v].f+=val;
                return;
            }
            int mid=(l+r)/2;
            if(pos<=mid) update(pos,val,l,mid,v*2);
            else update(pos,val,mid+1,r,v*2+1);
            st[v]=max(st[v*2],st[v*2+1]);
        }
        pair<int,int> query(int tl,int tr,int l=0,int r=n-1,int v=1){
            if(r<tl or tr<l){
                return {-1,-1};
            }
            if(tl<=l and r<=tr){
                return st[v];
            }
            int mid=(l+r)/2;
            return max(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
        }
        int q(int l,int r){
            if(l<=0 and r>=n-1){
                l=0,r=n-1;
            }
            if(r<0){
                l+=n;
                r+=n;
            }
            if(l>=n){
                l-=n;
                r-=n;
            }
            if(l<0){
                l+=n;
                auto p=query(l,n-1);
                p=max(p,query(0,r));
                return (p.f==-1?-1:p.f);
            }
            else if(r>=n){
                r-=n;
                auto p=query(l,n-1);
                p=max(p,query(0,r));
                return (p.f==-1?-1:p.f);
            }
            else{
                auto p=query(l,r);
                return (p.f==-1?-1:p.f);
            }
        }
    };
    vector<int> ord,rev;
    vector<int> st,en;
}

void init(int k, std::vector<int> r) {
    int n=(int)r.size();
    segtree T1(n);
    segtree T2(n);
    segtree2 T3(n);
    vector<vector<int>>adj(n);
    T1.init();
    T2.init();
    for(int i=0;i<n;i++){
        T1.update(i,i,r[i]);
        T2.update(i,i,inf);
        T3.update(i,-1);
    }
    vector<int> par(n);
    for(int t=0;t<n;t++){
        while(T1.st[1].f==0){
            int i=T1.st[1].s;
            //cout<<"i "<<i<<'\n';
            T1.update(i,i,inf);
            T2.update(i,i,-inf);
            T2.add(i+1,i+k-1,1);
        }
        int pos=T2.st[1].s;
        int p=T3.q(pos,pos+k-1);
        par[pos]=(p==-1?-1:ord[p]);
        //cout<<(p==-1?-1:ord[p])<<' '<<pos<<'\n';
        if(p!=-1) adj[ord[p]].push_back(pos);
        //cout<<pos<<'\n';
        ord.push_back(pos);
        T2.update(pos,pos,inf);
        T2.add(pos+1,pos+k-1,-1);
        T1.add(pos-k+1,pos-1,-1);
        T3.update(pos,(int)ord.size());
    }
    st=vector<int>(n);
    en=vector<int>(n);
    int timer=0;
    function<void(int)> dfs=[&](int v){
        st[v]=++timer;
        for(auto u:adj[v]){
            dfs(u);
        }
        en[v]=timer;
    };
    for(int i=0;i<n;i++){
        if(par[i]==-1) dfs(i);
    }
	return;
}

int compare_plants(int x, int y) {
    if(st[x]<=st[y] and en[y]<=en[x]) return 1;
    else if(st[y]<=st[x] and en[x]<=en[y]) return -1;
    return 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