Untitled
unknown
c_cpp
2 years ago
1.1 kB
7
Indexable
#include <iostream>
#include <vector>
#include <unordered_set>
#include <map>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int> > vp;
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
vp.push_back(make_pair(a,b));
}
sort(vp.begin(), vp.end());
vector<int> min_up_p(n + 1);
min_up_p[n] = INT_MAX;
for (int i = n - 1; i >= 0; --i) {
min_up_p[i] = min(min_up_p[i + 1], vp[i].second);
}
// for (int i = 0; i < n + 1; ++i) {
// cout << min_up_p[i] << " ";
// }
// cout << endl;
int ans = 0;
int max_right = INT_MIN;
for (int i = 0; i < n; ++i) {
//cout << vp[i].second << " " << max_right << " " << min_up_p[i + 1] << " ";
if (vp[i].second > max_right && vp[i].second < min_up_p[i + 1]) {
++ans;
}
max_right = max(max_right, vp[i].second);
}
//cout << endl;
cout << ans;
return 0;
}Editor is loading...
Leave a Comment