AcWing 1978. 奶牛过马路
原题链接
简单
作者:
imnoob
,
2022-01-10 21:45:02
,
所有人可见
,
阅读 277
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
typedef pair<int, int> PII;
int d[N], f[N];
int main()
{
int t;
cin >> t;
vector<PII> q;
for(int i = 0;i < t;i ++){
int a, b;
cin >> a >> b;
q.push_back({a, b});
}
sort(q.begin(), q.end());
f[1] = q[0].second, d[t] = q[t - 1].second;
for(int i = 2;i <= t;i ++)
f[i] = max(f[i - 1], q[i - 1].second);
for(int i = t - 1;i >= 1;i --)
d[i] = min(d[i + 1], q[i - 1].second);
int ans = t;
for(int i = 1;i <= t;i ++){
if(q[i - 1].second < f[i] || q[i - 1].second > d[i])
ans --;
}
cout << ans;
}