Pagini recente » Cod sursa (job #1377739) | Cod sursa (job #2667108) | Cod sursa (job #2764701) | Cod sursa (job #2608580) | Cod sursa (job #25795)
Cod sursa(job #25795)
#include <stdio.h>
const int N_MAX = 400010;
int v[N_MAX], q[N_MAX];
int main()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
int N, k, i;
scanf("%d\n", &N);
for (i = 1; i <= N; i ++) {
scanf("%d %d\n", &v[i], &k);
if (k == 0) {
v[i] *= (-1);
}
}
for (i = 1; i <= N; i ++) {
v[N + i] = v[i];
}
for (i = 1; i <= 2 * N; i ++) {
v[i] = v[i - 1] + v[i];
}
int n = N * 2, beg = 1, sf = 1;
int L = 0, inc = 0, sfr = 0, dif;
//deque
q[1] = 1;
for (i = 2; i <= n; i ++) {
while (q[beg] <= i - N && beg <= sf) {
beg ++;
}
while (sf >= beg && v[i] < v[q[sf]]) {
sf --;
}
q[++ sf] = i;
dif = v[q[sf]] - v[q[beg]];
if (dif > L) {
L = dif;
inc = q[beg] + 1;
sfr = q[sf];
} else {
if (dif == L) {
if (q[beg] + 1 < inc) {
inc = q[beg] + 1;
sfr = q[sf];
} else {
if (q[beg + 1] == inc) {
if (q[sf] < sfr) {
sfr = q[sf];
}
}
}
}
}
}
printf("%d %d %d\n", L, inc, sfr - inc + 1);
return 0;
}