2015年3月21日 星期六

2015/03/21 POI 21th Salad bar

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

typedef pair<int, int> HI;
#define h first
#define i second

deque<HI> deq;

int N;
char c[2000000];

bool cmp(HI a, HI b)
{
    return a.h <= b.h;
}

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

    scanf("%s", c);

    deq.push_front(HI(0, -1) );
    int now = 0;

    int Ans = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        if( c[Ni] == 'p' ) now++;
        else now--;

        HI tmp = HI(now, Ni);

        while( deq.size() > 1 && tmp > deq[0] && deq[0] > deq[1] ) deq.pop_front();
        while( deq.size() > 1 && tmp < deq[0] && deq[0] < deq[1] ) deq.pop_front();
        while( deq.size() > 2 && tmp > deq[0] && cmp(deq[2], deq[0]) && cmp(deq[1], tmp) ) deq.pop_front(), deq.pop_front();
        while( deq.size() > 2 && tmp < deq[0] && cmp(deq[0], deq[2]) && tmp < deq[1] ) deq.pop_front(), deq.pop_front();

        if( tmp > deq[0] ) Ans = max(Ans, tmp.i-deq[0].i);

        deq.push_front(tmp);
    }

    printf("%d\n", Ans);
}

沒有留言:

張貼留言