Koishi Loves Segments

题目描述

Koishi喜欢线段。

她的nn条线段都能表示成数轴上的某个闭区间[l,r][l,r]。Koishi喜欢在把所有线段都放在数轴上，然后数出某些点被多少线段覆盖了。

Flandre看她和线段玩得很起开心，就抛给她一个问题：

数轴上有mm个点突然兴奋，如果自己被身上覆盖了超过xx条线段，这个点就会浑身难受然后把Koishi批判一番。

Koishi十分善良，为了不让数轴上的点浑身难受，也为了让自己开心，她想在数轴上放入尽量多的线段。

按照套路，Koishi假装自己并不会做这道题，所以她就来求你帮忙。并承诺如果你解决了问题就给你打一通电话w。

输入格式

第一行两个个整数n,mn,m，分别表示插入的线段数和关键点数。

接下来nn行，每行两个整数l,r(lleq r)l,r(l≤r)，表示线段[l,r][l,r]的端点。

接下来mm行，每行两个整数p,xp,x，表示有个位于pp的点突然兴奋，并认为自己身上不得覆盖超过xx条线段

输出格式

一个整数，表示最多能放入的线段数

输入输出样例

输入 #1复制

4 3
1 3
2 4
5 7
6 8
2 5
3 1
6 2

输出 #1复制

3

说明/提示

对于20%的数据，满足1leq n,mleq 201≤n,m≤20

对于60%的数据，满足1leq n,mleq 1001≤n,m≤100

对于80%的数据，满足1leq n,mleq 50001≤n,m≤5000

对于100%的数据，满足1leq xleq nleq 2*10^5,1leq mleq 4*10^5,|l|,|r|,|p|leq 10^71≤x≤n≤2∗105,1≤m≤4∗105,∣l∣,∣r∣,∣p∣≤107

如果一个点兴奋了两次，那么Koishi应当满足它的*较严苛的要求*（也就是pp相同时xx取最小值啦）

请适当使用读入优化

#include <bits/stdc++.h>                                                                                               77

using namespace std;
typedef long long ll;
int T;
const int maxn=5e5+5;
struct atom{
    int l,r;
    bool operator<(const atom& s)const {
        return l<s.l;
    }
}o[maxn],c[maxn];
int n,m;
multiset<int>st;
int main()
{
    scanf("%d%d",&n,&m);
    for(register int i=1;i<=n;++i){
        scanf("%d%d",&o[i].l,&o[i].r);
    }
    int res=n;
    for(register int i=1;i<=m;++i){
        scanf("%d%d",&c[i].l,&c[i].r);
    }
    sort(o+1,o+1+n);
    sort(c+1,c+1+m);
    for(register int i=1,j=1;i<=m;++i){
        while(j<=n&&o[j].l<=c[i].l){
            st.insert(o[j].r);
            ++j;
        }
        while(st.size()&&*st.begin()<c[i].l){
            st.erase(st.begin());
        }
        while(st.size()>c[i].r){
            st.erase(--st.end());
            --res;
        }
    }
    printf("%d
",res);
    return 0;
}