Cod sursa(job #1510892)

Utilizator mirupetPetcan Miruna mirupet Data 25 octombrie 2015 18:44:01
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<cstdio>
#include<deque>
#define DIM 400001
#define SET(x) (x ? 1 : - 1)
using namespace std;

int N, X, Y, NR, POS, MAX;
int i;
int v[DIM];
deque <int> deq, pos;

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

        scanf("%d", &N);

        for (i = 1; i <= N; i++)
        {
            scanf("%d%d", &X, &Y);
            v[i] = v[i - 1] + SET(Y) * X;
            v[i + N] = SET(Y) * X;
        }

        for (i = N + 1; i <= 2 * N; i++)
            v[i] += v[i - 1];

        for (i = 1; i <= 2 * N; i++)
        {
            while (!pos.empty() && i - pos.front() > N)
            {
                deq.pop_front();
                pos.pop_front();
            }

            while (!deq.empty() && deq.back() > v[i])
            {
                deq.pop_back();
                pos.pop_back();
            }

            deq.push_back(v[i]);
            pos.push_back(i);

            if (v[i] - deq.front() > MAX)
            {
                MAX = v[i] - deq.front();
                POS = pos.front() + 1;
                NR = i - pos.front();
            }

            if (v[i] - deq.front() == MAX)
            {
                if (pos.front() + 1 < POS)
                {
                    POS = pos.front() + 1;
                    NR = i - pos.front();
                }
                else
                    if (pos.front() + 1 == POS && i - pos.front() < NR)
                        NR = i - pos.front();
            }
        }

        printf("%d %d %d", MAX, POS, NR);

    }