Submission #1007694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007694		Ahmed57	Comparing Plants (IOI20_plants)	C++17	100 / 100	863 ms	159672 KiB

plants

#include "bits/stdc++.h"
//#include "plants.h"

using namespace std;
#define int long long
pair<int,int> seg[800001];
int lazy[800001];
vector<int> arr;
void build(int p,int l,int r){
    if(l==r){
        seg[p] = {arr[l],l};
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);
    build(p*2+1,md+1,r);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
void prop(int p,int l,int r){
    seg[p].first+=lazy[p];
    if(l!=r){
        lazy[p*2]+=lazy[p];
        lazy[p*2+1]+=lazy[p];
    }
    lazy[p] = 0;
}
void update(int p,int l,int r,int lq,int rq,int val){
    prop(p,l,r);
    if(l>=lq&&r<=rq){
        lazy[p]+=val;
        prop(p,l,r);
        return ;
    }
    if(r<lq||l>rq)return ;
    int md = (l+r)/2;
    update(p*2,l,md,lq,rq,val);
    update(p*2+1,md+1,r,lq,rq,val);
    seg[p] = min(seg[p*2],seg[p*2+1]);
}
pair<int,int> query(int p,int l,int r,int lq,int rq){
    prop(p,l,r);
    if(l>=lq&&r<=rq)return seg[p];
    if(r<lq||l>rq)return {1e9,0};
    int md = (l+r)/2;
    return min(query(p*2,l,md,lq,rq),query(p*2+1,md+1,r,lq,rq));
}
int idx = 0,k,n;
vector<int> h;
int bad(int x){
    int l = x-k+1 , r = x-1;
    if(r==-1){
        l+=n;r+=n;
        pair<int,int> val = query(1,0,n-1,l,r);
        if(val.first==0)return val.second;
        return -1;
    }else{
        pair<int,int> val = query(1,0,n-1,max(0ll,l),r);
        if(l<0){
            l+=n;
            val = min(val,query(1,0,n-1,l,n-1));
        }
        if(val.first==0)return val.second;
        return -1;
    }
}
void fix(){
    pair<int,int> x = query(1,0,n-1,0,n-1);
    if(x.first<0){
        update(1,0,n-1,x.second,x.second,1e9);
    }else return ;
    fix();
}
void buld(int x){
    while(bad(x)!=-1){
        buld(bad(x));
    }
    int l = x-k+1 , r = x;
    update(1,0,n-1,max(0ll,l),r,-1);
    if(l<0){
        l+=n;
        update(1,0,n-1,l,n-1,-1);
    }
    h[x] = idx--;
    fix();
}
int li[200001][20];
int ri[200001][20];
int PL[200001][20];
int PR[200001][20];
void init(int32_t K, vector<int32_t> r){
    idx = r.size();
    n = r.size();
    k = K;
    for(int i = 0;i<n;i++){
        arr.push_back(r[i]);
        h.push_back(-1);
    }
    build(1,0,n-1);
    while(seg[1].first==0){
        buld(seg[1].second);
    }
    for(int i = 0;i<n;i++){
        if(h[i]==-1){
            assert(0);
        }
    }
    multiset<pair<int,int>> s;
    for(int i = 0;i<k-1;i++){
        s.insert({h[i],i});
    }
    for(int i = n-1;i>=0;i--){
        auto it = s.lower_bound(make_pair(h[i],0));
        if(it==s.begin()){
            ri[i][0] = 0;
            PR[i][0] = i;
        }else{
            it--;
            PR[i][0] = (*it).second;
            ri[i][0] = ((*it).second-i+n)%n;
        }
        int nah = (i+k-1)%n;
        s.erase(s.lower_bound(make_pair(h[nah],nah)));
        s.insert({h[i],i});
    }
    s.clear();
    for(int i = n-k+1;i<n;i++){
        s.insert({h[i],i});
    }
    for(int i = 0;i<n;i++){
        auto it = s.lower_bound(make_pair(h[i],0));
        if(it==s.begin()){
            li[i][0] = 0;
            PL[i][0] = i;
        }else{
            it--;
            PL[i][0] = (*it).second;
            li[i][0] = (i-(*it).second+n)%n;
        }
        int nah = (i-k+1+n)%n;
        s.erase(s.lower_bound(make_pair(h[nah],nah)));
        s.insert({h[i],i});
    }
    for(int j = 1;j<20;j++){
        for(int i = 0;i<n;i++){
            PL[i][j] = PL[PL[i][j-1]][j-1];
            PR[i][j] = PR[PR[i][j-1]][j-1];
            li[i][j] = li[i][j-1]+li[PL[i][j-1]][j-1];
            ri[i][j] = ri[i][j-1]+ri[PR[i][j-1]][j-1];
        }
    }
}
bool lol(int x,int y){
    if(x<y){
        int st = x;
        int cur = x;
        for(int i = 19;i>=0;i--){
            if(st+ri[cur][i]<y){
                st+=ri[cur][i];
                cur = PR[cur][i];
            }
        }
        st+=ri[cur][0];
        if(st>=y&&h[y]<=h[st%n])return 1;
        st = x;cur = x;
        y-=n;
        for(int i = 19;i>=0;i--){
            if(st-li[cur][i]>y){
                st-=li[cur][i];
                cur = PL[cur][i];
            }
        }
        st-=li[cur][0];
        if(st<=y&&h[((y%n)+n)%n]<=h[((st%n)+n)%n])return 1;
    }else{
        int st = x;
        int cur = x;
        y+=n;
        for(int i = 19;i>=0;i--){
            if(st+ri[cur][i]<y){
                st+=ri[cur][i];
                cur = PR[cur][i];
            }
        }
        st+=ri[cur][0];
        if(st>=y&&h[y%n]<=h[st%n])return 1;
        st = x;cur = x;
        y-=n;
        for(int i = 19;i>=0;i--){
            if(st-li[cur][i]>y){
                st-=li[cur][i];
                cur = PL[cur][i];
            }
        }
        st-=li[cur][0];
        if(st<=y&&h[((y%n)+n)%n]<=h[((st%n)+n)%n])return 1;
    }
    return 0;
}
int32_t compare_plants(int32_t x, int32_t y){
    if(lol(x,y))return 1;
    if(lol(y,x))return -1;
    return 0;
}

• 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