제출 #791082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791082		alexander707070	식물 비교 (IOI20_plants)	C++14	0 / 100	1 ms	308 KiB

plants

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

int n,maxs,perm[MAXN];

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 init(int k,vector<int> r){
    n=int(r.size());

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

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

        for(int f=0;f<n;f++){
            if(getmin(1,0,n-1,f,f)==0 and mins(f-k+1,f-1)==0){
                maxs=f;
            }
        }

        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;
}

• 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