Cod sursa(job #1809969)

Utilizator silkMarin Dragos silk Data 19 noiembrie 2016 14:31:57
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstdio>
#define NMax 200000
#define ll long long

ll sum[2*NMax+1];
int deque[2*NMax+1];
int v[2*NMax+1];
int N;

void Read()
{
    int i,x,t;

    scanf("%d",&N);
    for(i = 1; i <= N; ++i)
    {
        scanf("%d %d",&x,&t);
        if(t) v[i] = x;
        else v[i] = -x;
    }

    for(i = N+1; i <= 2*N; ++i) v[i] = v[i-N];
    for(i = 1; i <= 2*N; ++i) sum[i] = sum[i-1] + v[i];
}

int main(){
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);

    int i,inc,sf,S,P,L;

    Read();
    inc = 0;
    sf = 0;
    for(S = -NMax, i = 1; i <= N; ++i)
    {
        if( sum[i] - sum[ deque[inc] ] > S ) { S = sum[i] - sum[ deque[inc] ]; P = deque[inc] + 1; L = i - P + 1; }

        while( sf>=inc && sum[i] < sum[ deque[sf] ] ) --sf;
        deque[++sf] = i;
    }
    if( !deque[inc] ) ++inc;

    for(i = N+1; i <= 2*N; ++i)
    {
        if( sum[i] - sum[ deque[inc] ] > S ) { S = sum[i] - sum[ deque[inc] ]; P = deque[inc] + 1; L = i - P + 1; }

        while( sf>=inc && deque[inc] <= i-N ) ++inc;
        while( sf>=inc && sum[i] < sum[ deque[sf] ] ) --sf;
        deque[++sf] = i;
    }

    printf("%d %d %d\n",S,P,L);



return 0;
}