cjb-poi2011temperature

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
int n;
int l[2100000],r[2100000];
int q[2100000];
int main()
{
    cin>>n;
    rep(i,n)scanf("%d%d",&l[i],&r[i]);
    int ans=1;
    int head=1,tail=1;
    q[1]=1;
    for(int i=2;i<=n;i++)
    {
        while (head<=tail && l[q[tail]]<l[i])tail--; q[++tail]=i;
        while (head<=tail && l[q[head]]>r[i])head++;
        ans=max(ans,i-q[head-1]);
    }
    cout<<ans<<endl;
}
}}}

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#define rep(i,n) for(int i=1;i<=n;i++)
#define mp make_pair
#define pb push_back
using namespace std;
#define PI 3.1415926535897932384626433
#define N 1000010
#define LF double
#define stack stck
int n;
int l[2100000],r[2100000];
int q[2100000];
int main()
{
    cin>>n;
    rep(i,n)scanf("%d%d",&l[i],&r[i]);
    int ans=1;
    int head=1,tail=1;
    q[1]=1;
    for(int i=2;i<=n;i++)
    {
        while (head<=tail && l[q[tail]]<l[i])tail--; q[++tail]=i;
        while (head<=tail && l[q[head]]>r[i])head++;
        ans=max(ans,i-q[head-1]);
    }
    cout<<ans<<endl;
}