Pagini recente » Cod sursa (job #2870901) | Cod sursa (job #2899159) | Cod sursa (job #933761) | Cod sursa (job #578129) | Cod sursa (job #2487351)
#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;
}