比赛 |
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;
}