Cod sursa(job #2487351)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 4 noiembrie 2019 17:00:04
Problema Ciurul lui Eratosthenes Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.38 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("drept2.in");
ofstream fout("drept2.out");

long long N, M, A, B, POZ, LUNG, DLUNG;

deque<pair<long long, long long>> minDrA;
deque<pair<long long, long long>> maxStA;
deque<pair<long long, long long>> minDrB;
deque<pair<long long, long long>> maxStB;

int main()
{
    fin >> M >> N >> A >> B >> POZ >> LUNG;

    minDrA.push_back({POZ + LUNG - 1, 1});
    maxStA.push_back({POZ, 1});

    minDrB.push_back({POZ + LUNG - 1, 1});
    maxStB.push_back({POZ, 1});

    long long ans = 0;

    for(long long i = 2; i <= N; ++i)
    {
        fin >> POZ >> DLUNG;

        long long stanga = POZ;

        LUNG += DLUNG;

        long long dreapta =  POZ + LUNG - 1;

        //***************************************************************
        while(minDrA.empty() == false && minDrA.back().first >= dreapta)
            minDrA.pop_back();

        minDrA.push_back({dreapta, i});

        if(minDrA.front().second + A == i)
            minDrA.pop_front();


        //****************************************************************
        while(minDrB.empty() == false && minDrB.back().first >= dreapta)
            minDrB.pop_back();

        minDrB.push_back({dreapta, i});

        if(minDrB.front().second + B == i)
            minDrB.pop_front();


        //*****************************************************************
        while(maxStA.empty() == false && maxStA.back().first <= stanga)
            maxStA.pop_back();

        maxStA.push_back({stanga, i});

        if(maxStA.front().second + A == i)
            maxStA.pop_front();


        //*****************************************************************
        while(maxStB.empty() == false && maxStB.back().first <= stanga)
            maxStB.pop_back();

        maxStB.push_back({stanga, i});

        if(maxStB.front().second + B == i)
            maxStB.pop_front();


        if(i >= A)
        {
            long long intersectie = minDrA.front().first - maxStA.front().first + 2 - B;

            if(intersectie > 0) ans += intersectie;

        }

        if(i >= B)
        {
            long long intersectie = minDrB.front().first - maxStB.front().first + 2 - A;

            if(intersectie > 0) ans += intersectie;
        }
    }

    if(A == B) fout << ans/2;
    else fout << ans;
}