Untitled
#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; }
Leave a Comment