Untitled

 avatar
unknown
c_cpp
a year ago
1.1 kB
3
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;
}
Leave a Comment