Submission #18549

#	Time	Username	Problem	Language	Result	Execution time	Memory
18549		eaststar	Global Warming (NOI13_gw)	C++14	0 / 40	1000 ms	24516 KiB

gw

#include <stdio.h>
#include <algorithm>
using namespace std;
struct data{
    int h,i;
    bool operator<(const data&r)const{
        if(h==r.h)return i<r.i;
        return h<r.h;
    }
}a[1000010];
int s[1000010],e[1000010],b[1000010],c[1000010],m,t,ans;
int main(){
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;++i)scanf("%d",&a[i].h),a[i].i=i;
    sort(a+1,a+n+1);
    if(!a[n].h){
        puts("0");
        return 0;
    }
    s[ans=m=1]=1,e[1]=n;
    for(i=1;i<=n;){
        for(;;++i){
            for(j=1,t=0;j<=m;++j){
                if(s[j]<=a[i].i&&a[i].i<=e[j]){
                    if(s[j]<a[i].i)b[++t]=s[j],c[t]=a[i].i-1;
                    if(a[i].i<e[j])b[++t]=a[i].i+1,c[t]=e[j];
                }
                else b[++t]=s[j],c[t]=e[j];
            }
            for(j=1;j<=t;++j)s[j]=b[j],e[j]=c[j];
            m=t;
            if(a[i].h!=a[i+1].h)break;
        }
        if(ans<m)ans=m;
    }
    printf("%d",ans);
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11