# Cod sursa(job #30323)

Utilizator Data 13 martie 2007 19:09:31 Buline 90 cpp done Arhiva de probleme 1.53 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;

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

int i, val, semn;

scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf("%d %d", &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()
{