记录编号	565040	评测结果	AAAAAAAAAA
题目名称	平凡的题面	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.209 s
提交时间	2021-10-15 20:54:13	内存使用	4.58 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
ll ans;
int vc;
int nc,mc;
int n[100001];
struct zpy
{
    int l;
    int r;
}s[100001];
int sj;
int b[200001];
int a[1000001],aj;
void ad(int x)
{
    a[++aj]=x;
    int ch=aj;
    while(ch!=1&&a[ch]<a[ch>>1])
    {
        swap(a[ch],a[ch>>1]);
        ch>>=1;
    }
    return;
} 
void sc()
{
    a[1]=a[aj];
    aj--;
    int f=1;
    int ch=2;
    while(ch<=aj)
    {
        if(ch+1<=aj&&a[ch+1]<a[ch]) ch++;
        if(a[f]>a[ch]) swap(a[f],a[ch]);
        else break;
        f=ch;
        ch<<=1;
//        cout<<"sc:"<<ch<<" "<<aj<<endl;
    }
    return;
}
bool cmp(zpy x,zpy y)
{
    return x.l<y.l;
}
void cl()
{
    sj=1;
    for(int i=s[1].l;i<=vc;i++)
    {
        while(s[sj].l==i)
        {
            ad(s[sj].r);
            sj++;
        }
//        cout<<"P1\n";
        ///添加区间 
        while(b[i]&&aj)
        {
            ans++;
//            cout<<b[i]<<" "<<aj<<endl;
            sc();
            b[i]--;
        }
//        cout<<"P2\n";
        ///减去区间
//        
//        cout<<i<<":"<<ans<<" "<<a[1]<<" "<<aj<<" "<<b[i]<<" "<<endl;
        while(aj&&a[1]<=i) sc();
        ///淘汰过时区间 
//        cout<<i<<":"<<ans<<" "<<a[1]<<" "<<aj<<" "<<b[i]<<" "<<endl;
    }
    return;
}
int main()
{
    freopen("bg.in","r",stdin);
	freopen("bg.out","w",stdout);
	cin>>nc>>mc;
	for(int i=1;i<=nc;i++)
	{
	    scanf("%d",&n[i]);
	    b[n[i]]++;
	    vc=max(vc,n[i]);
    }
    for(int i=1;i<=mc;i++)
    {
        scanf("%d%d",&s[i].l,&s[i].r);
    }
    sort(s+1,s+mc+1,cmp);
    cl();
    cout<<ans<<endl;
    return 0;
}
//7 7
//6 17 16 27 44 28 29
//1 20
//5 30