Guest User

Untitled

a guest
Mar 8th, 2019
116
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.67 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 1e6 + 5;
  6. int maxx[N];
  7.  
  8. int main() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.     cout.tie(nullptr);
  12.     cerr.tie(nullptr);
  13.     int n;
  14.     cin >> n;
  15.     vector<pair<int, int>> v(n);
  16.     for (auto& e : v) {
  17.         cin >> e.first >> e.second;
  18.     }
  19.     sort(v.begin(), v.end());
  20.  
  21.     maxx[n-2] = v[n-1].second;
  22.  
  23.     for (int i = n-2; i>=1; i--) {
  24.         maxx[i-1] = max(maxx[i], v[i].second);
  25.     }
  26.  
  27.     int sol = 1;
  28.  
  29.     for (int i = 0; i<n-1; i++) {
  30.         if (v[i].second > maxx[i]) {
  31.             sol++;
  32.         }
  33.     }
  34.  
  35.     cout << sol << endl;
  36.     return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment