Submission #3020138

---

Source Code Expand

//#pragma GCC optimize(3)
#include<iostream>
#include<iomanip>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set> 
#include<map>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define ll long long
#define db double
#define inf 200001
#define infm 800009
#define INF (int)1e9
#define mod 1000000007LL
#define pi acos(-1)
#define rd(n) {n=0;char ch;int f=0;do{ch=getchar();if(ch=='-'){f=1;}}while(ch<'0'||ch>'9');while('0'<=ch&&ch<='9'){n=(n<<1)+(n<<3)+ch-48;ch=getchar();}if(f)n=-n;}
using namespace std;
int n,m;
 
vector <int> a[inf];
priority_queue <int,vector<int>,greater<int> > q;
int p[inf];
 
int main(){
    rd(n) rd(m)
    int x,y;
    for (int i=1;i<=n;i++){
        rd(x) rd(y)
        a[x].push_back(y);
    }
    int nowL=0,nowR=m+1;
    for (int i=1;i<=m;i++){
        for (int j=0;j<a[i].size();j++){
            int now=a[i][j];
            if (nowL<i){
                nowL++;
                q.push(now);
            }
            else{
                int tmp=q.top();
                (now>tmp)?(q.pop(),q.push(now),p[tmp]++):p[now]++;
            }
        }
    }
    for (int i=0;i<a[0].size();i++){
        p[a[0][i]]++;
    }
    int ans=p[m+1];
    for (int i=m;i>=1;i--){
        for (;p[i];p[i]--){
            (nowR>i && nowR-1>nowL)?nowR--:ans++;
        }
    }
    printf("%d\n",ans);
    return 0;
}

Submission Info

Judge Result