Submission #640399

#	Time	Username	Problem	Language	Result	Execution time	Memory
640399		lis05st	Comparing Plants (IOI20_plants)	C++17	5 / 100	93 ms	41272 KiB

plants

#ifdef LIS05ST
    #define _GLIBCXX_DEBUG
    #define _GLIBCXX_DEBUG_PEDANTIC
#endif
#pragma GCC optimize("O3")
#pragma GCC target("avx2,popcnt,lzcnt")
#include"plants.h"
#include"bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef long double ld;

const int NMAX=6e5;
int pref[NMAX+5];
int n,k;

int get(int l,int r){
    return pref[r]-pref[l-1];
}
bool one(int l,int r){
    return get(l,r)==r-l+1;
}
bool zero(int l,int r){
    return get(l,r)==0;
}
vector<int>h;
int id(int x){
    return (x%n+n)%n;
}


struct Node{
    int min;
    int pos;
    ll padd;
};
Node tree[4*NMAX+5];

Node merge(Node a,Node b){
    Node res;
    res.min=min(a.min,b.min);
    res.pos=-1;
    if(a.min==res.min){
        res.pos=max(res.pos,a.pos);
    }
    if(b.min==res.min){
        res.pos=max(res.pos,b.pos);
    }
    res.padd=0;
    return res;
}

vector<int>vec;
void build(int v,int l,int r){
    if(l==r){
        tree[v].min=vec[l];
        tree[v].pos=l;
        tree[v].padd=0;
        return;
    }
    int m=(l+r)/2;
    build(2*v,l,m);
    build(2*v+1,m+1,r);
    tree[v]=merge(tree[2*v],tree[2*v+1]);
}

void pushAdd(int v,int val){
    tree[v].min+=val;
    tree[v].padd+=val;
}
void push(int v,int l,int r){
    pushAdd(2*v,tree[v].padd);
    pushAdd(2*v+1,tree[v].padd);
    tree[v].padd=0;
}

pair<int,int> get(int v,int l,int r,int l0,int r0){
    push(v,l,r);
    if(r0<l||r<l0)return {1e9,1e9};
    if(l0<=l&&r<=r0)return {tree[v].min,tree[v].pos};
    int m=(l+r)/2;
    if(tree[2*v].min==0&&tree[2*v].pos>=l0)return get(2*v,l,m,l0,r0);
    return get(2*v+1,m+1,r,l0,r0);
}

void add(int v,int l,int r,int l0,int r0,int val){
    push(v,l,r);
    if(r0<l||r<l0)return;
    if(l0<=l&&r<=r0){
        pushAdd(v,val);
        return;
    }
    int m=(l+r)/2;
    add(2*v,l,m,l0,r0,val);
    add(2*v+1,m+1,r,l0,r0,val);
    tree[v]=merge(tree[2*v],tree[2*v+1]);
}

void add(int l,int r,int val){
    l-=2*n;r-=2*n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
    l+=n;r+=n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
    l+=n;r+=n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
    l+=n;r+=n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
    l+=n;r+=n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
    l+=n;r+=n;
    if(r>=0&&l<=3*n-1){
        int L=min(3*n-1,max(l,0));
        int R=min(3*n-1,max(r,0));
        add(1,0,3*n-1,L,R,val);
    }
}

void init(int K, std::vector<int> rr){
    n=rr.size();h.resize(n);
    k=K;
    for(int i=0;i<n;i++)pref[i+1]=pref[i]+rr[i];

    for(int e=0;e<3;e++)for(int i=0;i<n;i++){
        vec.push_back(rr[i]);
    }
    //for(auto e:vec)cout<<e<<" ";cout<<"\n";
    build(1,0,3*n-1);
    int L=0+n;int R=n-1+n;
    if(2*k<=n)return;
    for(int step=n;step>=1;step--){
        auto[val,pos]=get(1,0,3*n-1,L,R);
        //cout<<"step: "<<step<<"\n";
        //cout<<val<<":"<<pos<<endl;
        if(get(1,0,3*n-1,pos-k+1,pos-1).first!=0){
            h[pos%n]=step;
            add(pos-k+1,pos-1,-1);
            add(pos,pos,1e9);
        }else{
            auto [val2,pos2]=get(1,0,3*n-1,pos-k+1,pos-1);
            h[pos2%n]=step;
            add(pos2-k+1,pos2-1,-1);
            add(pos2,pos2,1e9);
        }
    }
    //for(auto e:h)cout<<e<<" ";cout<<endl;
};
int compare_plants(int x, int y){
    if(k==2){
        x++,y++;
        if(zero(x,y-1))return 1;
        if(one(1,x-1)&&one(y,n))return 1;
        if(one(x,y-1))return -1;
        if(zero(1,x-1)&&zero(y,n))return -1;
        return 0;
    }
    if(h[x]>h[y])return 1;
    if(h[x]<h[y])return -1;
    return 0;
}

#define MULTITESTS false
void solve(int testCase){

}

           
//   x     y


void precalc(){

}
/*
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    precalc();
    int t=1;
    if(MULTITESTS)cin>>t;
    for(int i=1;i<=t;i++){
        auto t1=clock();
        solve(i);
        auto t2=clock();
        float delta=t2-t1;
        delta/=CLOCKS_PER_SEC;
        #ifdef LIS05ST
        cout<<"("<<i<<")------------"<<fixed<<setprecision(2)<<delta<<"s\n";
        #endif
    }
}*/

• Subtask 1: 5 / 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