比赛 2024暑期C班集训4 评测结果 AAAAAWWEEE
题目名称 梦境 最终得分 50
用户昵称 darkMoon 运行时间 2.457 s
代码语言 C++ 内存使用 3.95 MiB
提交时间 2024-07-04 08:31:48
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
ifstream fin("dream.in");
ofstream fout("dream.out");
auto mread = [](){int x;fin >> x;return x;};
const int N = 2e5 + 5;
int n = mread(), m = mread(), t[N], now, s[N];
pair<int, int> p[N];
map<int, int> ap;
void add(int x, int k){
    while(x <= now){
        s[x] += k;
        x += x & -x;
    }
    return;
}
int query(int x){
    int ans = 0;
    while(x){
        ans += s[x];
        x -= x & -x;
    }
    return ans;
}
signed main(){
    for(int i = 1; i <= n; i ++){
        p[i].fi = mread(), p[i].se = mread();
        ap[p[i].fi] = 1, ap[p[i].se] = 1;
    }
    for(int i = 1; i <= m; i ++){
        t[i] = mread();
        ap[t[i]] = 1;
    }
    for(auto &t : ap){
        t.se = ++now;
    }
    for(int i = 1; i <= n; i ++){
        p[i].fi = ap[p[i].fi], p[i].se = ap[p[i].se];
        // printf("*** %lld %lld\n", p[i].fi, p[i].se);
    }
    for(int i = 1; i <= m; i ++){
        t[i] = ap[t[i]];
        // printf("*** %lld\n", t[i]);
    }
    sort(p + 1, p + 1 + n, [](pair<int, int> a, pair<int, int> b){
        if(a.se == b.se)
        return a.fi < b.fi;
        else
        return a.se < b.se;
    });
    sort(t + 1, t + 1 + m);
    int idx = 1, it = 1, ans = 0;
    auto solve = [&](int l, int r){
        if(query(r) - query(l - 1) == 0){
            return;
        }
        ans ++;
        int nl = l, nr = r, tmp = query(r);
        while(nl < nr){
            int mid = nl + nr >> 1;
            if(tmp - query(mid - 1) > 0)
            nr = mid;
            else
            nl = mid + 1;
        }
        add(nl, -1);
        return;
    };
    for(int i = 1; i <= now; i ++){
        while(idx <= m && t[idx] == i){
            add(t[idx ++], 1);
        }
        while(it <= n && p[it].se == i){
            solve(p[it].fi, p[it].se);
            it ++;
        }
    }
    fout << ans;
    return 0;
}