(POI) XVIII OI Round II - day 2 Task Temperature

https://szkopul.edu.pl/problemset/problem/WePkBWRjS5vpsqQxi9TldHB1/site/?key=statement

超級精湛的O(N)題XD。

#include <iostream>
#include <cstdio>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int,int> pii;
const int N = 1000006;

#define F first
#define S second

int L[N],R[N];

int main ()
{
    int n;
    scanf("%d",&n);
    for (int i=1;n>=i;i++)
    {
        scanf("%d %d",&L[i],&R[i]);
    }
    deque<pii> dq;  //first time stack save index!
    int ans=1;
    for (int i=1;n>=i;i++)
    {
        while (dq.size() && L[ dq.front().F ] > R[i])
        {
            dq.pop_front();
        }
        if (dq.size())
        {
            ans = max(ans,i - dq.front().S + 1);
        }
        int s = i;
        while (dq.size() && L[ dq.back().F ] <= L[i])
        {
            s = dq.back().S;
            dq.pop_back();
        }
        dq.push_back(make_pair(i,s));
    }
    printf("%d\n",ans);
}