Submission #791097

#	Time	Username	Problem	Language	Result	Execution time	Memory
791097		alexander707070	Comparing Plants (IOI20_plants)	C++14	27 / 100	985 ms	12620 KiB

plants

#include<bits/stdc++.h>
#define MAXN 200007
using namespace std;

int n,maxs,perm[MAXN],k;

int tree[4*MAXN],lazy[4*MAXN];

void psh(int v){
    tree[2*v]+=lazy[v];
    tree[2*v+1]+=lazy[v];

    lazy[2*v]+=lazy[v];
    lazy[2*v+1]+=lazy[v];

    lazy[v]=0;
}

void update(int v,int l,int r,int ll,int rr,int val){
    if(ll>rr)return;
    if(l==ll and r==rr){
        tree[v]+=val;
        lazy[v]+=val;
    }else{
        int tt=(l+r)/2;
        psh(v);

        update(2*v,l,tt,ll,min(tt,rr),val);
        update(2*v+1,tt+1,r,max(tt+1,ll),rr,val);
        tree[v]=min(tree[2*v],tree[2*v+1]);
    }
}

int getmin(int v,int l,int r,int ll,int rr){
    if(ll>rr)return n;
    if(l==ll and r==rr){
        return tree[v];
    }else{
        int tt=(l+r)/2;
        psh(v);

        return min( getmin(2*v,l,tt,ll,min(tt,rr)) , getmin(2*v+1,tt+1,r,max(tt+1,ll),rr) );
    }
}

int mins(int l,int r){
    if(l>=0)return getmin(1,0,n-1,l,r);
    return min( getmin(1,0,n-1,n+l,n-1) , getmin(1,0,n-1,0,r) );
}

void upgrade(int l,int r){
    if(l>=0)update(1,0,n-1,l,r,-1);
    else{
        update(1,0,n-1,n+l,n-1,-1);
        update(1,0,n-1,0,r,-1);
    }
}

void solve(int l,int r){

    if(l==r){
        if(mins(l-k+1,l-1)>0)maxs=l;
        return;
    }

    int tt=(l+r)/2;
    if(getmin(1,0,n-1,l,tt)==0){
        solve(l,tt);
    }else if(getmin(1,0,n-1,tt+1,r)==0){
        solve(tt+1,r);
    }
}

void init(int K,vector<int> r){
    n=int(r.size()); k=K;

    for(int i=0;i<n;i++){
        update(1,0,n-1,i,i,r[i]);
    }

    for(int i=n-1;i>=0;i--){

        solve(0,n/2-1);
        solve(n/2,n-1);

        perm[maxs]=i;
        upgrade(maxs-k+1,maxs-1);
        update(1,0,n-1,maxs,maxs,n-1);
    }
}

int compare_plants(int x, int y){
    if(perm[x]>perm[y])return 1;
    return -1;
}

/*
int main(){
    init(4,{3,0,0,0,1,2});
}
*/

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