Submission #1041642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041642		vjudge1	Comparing Plants (IOI20_plants)	C++17	100 / 100	566 ms	68204 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int n, pos[200100],CA;
vector<int> R;
set<int> CD;
set<pair<int,int>> gaps;
int bjl[200100][20],bjr[200100][20], gooverL[200100], gooverR[200100];
struct segtree{
    pair<int,int> T[1<<19];
    int lz[1<<20];
    inline void pd(int i){
        if(lz[i]){
            T[i].first+=lz[i];
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
            lz[i]=0;
        }
    }
    void init(int i,int l,int r){
        if(l==r)return void(T[i]={R[l],l});
        init(i*2,l,l+r>>1);
        init(i*2+1,l+r+2>>1,r);
        T[i]=min(T[i*2],T[i*2+1]);
    }
    void upd(int i,int l,int r,int ll,int rr){
        pd(i);if(ll<=l&&r<=rr)
            return lz[i]=-1,pd(i);
        if(l>rr||ll>r)return;
        upd(i*2,l,l+r>>1,ll,rr);
        upd(i*2+1,l+r+2>>1,r,ll,rr);
        T[i]=min(T[i*2],T[i*2+1]);
    }
    void upd2(int i,int l,int r,int ll,int rr){
        pd(i);if(ll<=l&&r<=rr)
            return lz[i]=1e9,pd(i);
        if(l>rr||ll>r)return;
        upd2(i*2,l,l+r>>1,ll,rr);
        upd2(i*2+1,l+r+2>>1,r,ll,rr);
        T[i]=min(T[i*2],T[i*2+1]);
    }
}ST;
inline int AGL(int k){
    return (k+n)%n;
}
inline void add(int i){
    if(!CD.size()){
        gaps.insert({n,i});
        CD.insert(i);
        return;
    }
    if(CD.size()==1){
        CD.insert(i);
        gaps.clear();
        int a=*CD.begin();
        int b=*--CD.end();
        gaps.insert({b-a,b});
        gaps.insert({n+a-b,a});
        return;
    }
    auto it1=CD.upper_bound(i);
    auto it2=it1;
    if(it2==CD.begin())
        it2=--CD.end();
    else --it2;
    if(it1==CD.end())
        it1=CD.begin();
    gaps.insert({AGL(i-*it2),i});
    gaps.insert({AGL(*it1-i),*it1});
    gaps.erase({AGL(*it1-*it2),*it1});
    CD.insert(i);
}
inline void del(int i){
    if(CD.size()==1)
        return CD.clear(),gaps.clear();
    else if(CD.size()==2){
        CD.erase(i);
        gaps.clear();
        gaps.insert({n,*CD.begin()});
        return;
    }
    auto it1=CD.upper_bound(i);
    auto it2=CD.find(i);
    if(it2==CD.begin())
        it2=--CD.end();
    else --it2;
    if(it1==CD.end())
        it1=CD.begin();
    gaps.erase({AGL(i-*it2),i});
    gaps.erase({AGL(*it1-i),*it1});
    gaps.insert({AGL(*it1-*it2),*it1});
    CD.erase(i);
}
inline int possiblemin(){
    auto[a,b]=ST.T[1];
    if(!a) {
        ST.upd2(1,0,n-1,b,b);
        add(b);
        return 1;
    }
    return 0;
}
void init(int k, std::vector<int> r) {
    R=r;
    k--;
    n=r.size();
    ST.init(1,0,n-1);
    while(possiblemin());
    while(CD.size()){
        int bst=(--gaps.end())->second;
        pos[bst]=++CA;
        if(bst<k)ST.upd(1,0,n-1,0,bst),
            ST.upd(1,0,n-1,bst-k+n,n-1);
        else ST.upd(1,0,n-1,bst-k,bst);
        while(possiblemin());
        del(bst);
    }
    set<pair<int,int>> st;
    st.insert({1e9,n});
    for(int i=n-k;i<n;i++)
        st.insert({pos[i],i});
    for(int i=0;i<n;i++)bjl[i][0]=st.upper_bound({pos[i],0})->second,
        st.erase({pos[(i+n-k)%n],(i+n-k)%n}),st.insert({pos[i],i});
    st.clear();
    for(int i=0;i<k;i++)
        st.insert({pos[i],i});
    st.insert({1e9,n});
    bjl[n][0]=bjr[n][0]=n;
    for(int i=n;i--;)bjr[i][0]=st.upper_bound({pos[i],0})->second,
        st.erase({pos[(i+k)%n],(i+k)%n}),st.insert({pos[i],i});
    for(int i=0;i<n;i++)
        if(bjl[i][0]>i&&bjl[i][0]-n)
            gooverL[i]=bjl[i][0],bjl[i][0]=i;
    for(int i=0;i<n;i++)
        if(bjr[i][0]<i&&bjr[i][0]-n)
            gooverR[i]=bjr[i][0],bjr[i][0]=i;
    for(int j=1;j<20;j++) for(int i=0;i<=n;i++)
        bjl[i][j]=bjl[bjl[i][j-1]][j-1],
        bjr[i][j]=bjr[bjr[i][j-1]][j-1];
    pos[n]=1e9;
    gooverL[n]=gooverR[n]=n;
}
int biggerl(int x,int y){
    int prevx=x;
    if(x<y)x=gooverL[bjl[x][19]];
    if(x<=y) return pos[bjl[prevx][19]]<=pos[y];
    for(int i=20;i--;)
        if(bjl[x][i]>y&&bjl[x][i]-n)
            x=bjl[x][i];
    if(bjl[x][0]==n)
        return 0;
    return pos[x]<=pos[y];
}
int biggerr(int x,int y){
    int prevx=x;
    if(x>y)x=gooverR[bjr[x][19]];
    if(x>=y) return pos[bjr[prevx][19]]<=pos[y];
    for(int i=20;i--;)
        if(bjr[x][i]<y&&bjr[x][i]-n)
            x=bjr[x][i];
    if(bjr[x][0]==n)
        return 0;
    return pos[x]<=pos[y];
}
inline int bigger(int x,int y){
    return biggerl(x,y)||biggerr(x,y);
}
int compare_plants(int x, int y) {
    if(pos[x]<pos[y])
        return bigger(x,y)?1:0;
    return bigger(y,x)?-1:0;
}

Compilation message (stderr)

plants.cpp: In member function 'void segtree::init(int, int, int)':
plants.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         init(i*2,l,l+r>>1);
      |                    ~^~
plants.cpp:23:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |         init(i*2+1,l+r+2>>1,r);
      |                    ~~~^~
plants.cpp: In member function 'void segtree::upd(int, int, int, int, int)':
plants.cpp:30:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         upd(i*2,l,l+r>>1,ll,rr);
      |                   ~^~
plants.cpp:31:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |         upd(i*2+1,l+r+2>>1,r,ll,rr);
      |                   ~~~^~
plants.cpp: In member function 'void segtree::upd2(int, int, int, int, int)':
plants.cpp:38:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |         upd2(i*2,l,l+r>>1,ll,rr);
      |                    ~^~
plants.cpp:39:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |         upd2(i*2+1,l+r+2>>1,r,ll,rr);
      |                    ~~~^~

• 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