2015年5月28日 星期四

2015/05/28 Codeforces 547B. Mike and Feet

// http://codeforces.com/problemset/problem/547/B
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

int Ans[300000];

set<int> r;
multiset<int> sz;

int N;
int A[300000];
int sp[300000];

bool cmp(int x, int y){ return A[x] < A[y]; }

int main()
{
    scanf("%d", &N);

    for(int Ni = 1; Ni <= N; Ni++)
    {
        scanf("%d", &A[Ni]);
        sp[Ni] = Ni;
    }

    sort(sp+1, sp+N+1, cmp);

    r.insert(0); r.insert(N+1);
    sz.insert(N);

    int now = N;

    for(int Ni = 1; Ni <= N; Ni++)
    {
        int i = sp[Ni];
        int x = *prev(r.upper_bound(i) );
        int y = *r.upper_bound(i);

        r.insert(i);
        sz.erase(sz.find(y-x-1) );
        sz.insert(i-x-1);
        sz.insert(y-i-1);

        int mx = *prev(sz.end() );

        while( now > mx ) Ans[now] = A[i], now--;
    }

    for(int Ni = 1; Ni <= N; Ni++)
    {
        printf("%d", Ans[Ni]);

        if( Ni == N ) puts("");
        else printf(" ");
    }
}

沒有留言:

張貼留言