【20180811】集训题d1
程序员文章站
2022-03-30 08:42:09
...
例行汇报比赛状况,今天打得情况总的来讲,我觉得还行,尽管分数没上200,rank也没进前10,但我自认为是我这几天打下来总体情况最好的一场了(虽然早上没吃早饭)。第一题第一眼看上去感觉要乱搞,然后看了看数据范围10e5,就有点懵了。再仔细一看10e5只有5分....剩下的10e3,就往n^2上去想了,然后就想到了贪心,出口按横坐标排序,人按纵坐标排序,然后从左往右扫,每个出口找纵坐标最近满足的那个,能够感性证明这个是对的。然后......我就想不出来了,我以为要用更为精妙的做法,结果其实就是贪心,只是把O(n)查找变成了用set维护后lowerbound查找。戏剧化的是有一部分人即使那么写了还是挂了,我对比了一下std然后合理怀疑......并不合理,set后面要加iterator?这个我是真的不知道。算了这5分不要也罢,可惜ac奖金了。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); }
template <typename T> void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}
set <int> st;
bool type[MAXN]; int pos[MAXN];
int main() {
int num;
read(num);
int n;read(n);
for(int i=1;i<=n;i++){
int x,y;
read(x),read(y);
type[x]=true,pos[x]=y;
}
for(int i=1;i<=n;i++){
int x,y;
read(x),read(y);
type[x]=false,pos[x]=y;
}
int ans=0;
for(int i=0;i<2*n;i++){
if(type[i])st.insert(pos[i]);
else{
set<int>::iterator tmp=st.lower_bound(pos[i]);
if(tmp==st.begin())continue;
tmp--;ans++;
st.erase(tmp);
}
}
writeln(ans);
return 0;
}