Cod sursa(job #30321)

Utilizator RaduPRadu Padurean RaduP Data 13 martie 2007 19:08:46
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define mp make_pair
#define x first
#define y second.first
#define z second.second

#define inf (int)(2*1e9+1)
#define Nmax 200005

int n;
long long v[Nmax];
long long Q[2*Nmax], E[2*Nmax], qe, qb;
pair< long long, pair<long long, long long> > best;

void readdata()
{
    freopen("buline.in", "r", stdin);
    freopen("buline.out", "w", stdout);
    
    int i, val, semn;
    
    scanf("%d", &n);
    for (i = 1; i <= n; ++i)
    {
        scanf("%lld %lld", &val, &semn);
        v[i] = !semn ? -val : val;
    }
}

void solve()
{
    int i;
    
    for (i = 1; i <= n; ++i)
        v[n+i] = v[i];
    
    for (i = 2; i <= 2*n; ++i)
        v[i] += v[i-1];
        
    best.x = -inf;    
    
    Q[qe = qb = 1] = E[qb] = 0;
    for (i = 1; i <= 2*n; ++i)
    {
        if (E[qb] < i-n) ++qb;
        
        if (v[i]-Q[qb] > best.x)
        {
            best.x = v[i]-Q[qb];
            best.y = E[qb]+1 > n ? E[qb]+1-n : E[qb]+1;
            best.z = i-E[qb];
        }
        else
        if (v[i]-qb == best.x && (E[qb]+1 > n ? E[qb]+1-n : E[qb]+1) < best.y)
        {
            best.y = E[qb]+1 > n ? E[qb]+1-n : E[qb]+1;
            best.z = i-E[qb];
        }
        
        while (qe >= qb && v[i] < Q[qe]) --qe;
        Q[++qe] = v[i], E[qe] = i;
    }
}

void writedata()
{
    printf("%lld %lld %lld\n", best.x, best.y, best.z);
}

int main()
{
    readdata();
    solve();
    writedata();
    return 0;
}