Cod sursa(job #25248)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 4 martie 2007 11:37:06
Problema Buline Scor 100
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 0.99 kb
#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;
				} 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;
}