Cod sursa(job #2549963)

Utilizator Gabi1623Ghita Gabriel Gabi1623 Data 18 februarie 2020 10:05:37
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <fstream>
#include <iostream>

using namespace std;

ifstream fin("buline.in");
ofstream fout("buline.out");

long long int  n,i,x,b,maxi, s, du, p, u;
long long int v[500001], d[500001];

int main()
{
    fin>>n;

    for (i=1; i<=n; i++)
    {
        fin>>x>>b;

        if (b==0)
            x = -x;
        v[i] = v[i-1] + x;
        v[i+n]=x;

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

    d[++u]=0;

    for (i=1; i<=n*2; i++)
    {
        while ( p<=u && v[i] < v[ d[u] ] )
            u--;

        d[++u] = i;

        if ( i - d[p] - 1 == n )
            p++;

        if ( v[i] - v[ d[p] ] > maxi)
        {
            maxi = v[i] - v[ d[p] ];
            s = d[p];
            du = i - s;
        }
    }
    fout<< maxi <<" "<< s+1 <<" "<< du ;
    return 0;
}