Advertisement
KShah

Untitled

Nov 21st, 2021
1,252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using std::vector;
  6. using std::cin;
  7. using std::cout;
  8. using std::pair;
  9.  
  10. struct Node{
  11.     long long cnt = 0;
  12.     int tl;
  13.     int tr;
  14.     int left = -1;
  15.     int right = -1;
  16.     Node(int l, int r) {
  17.         tl = l;
  18.         tr = r;
  19.     }
  20. };
  21.  
  22. class DynTree {
  23. private:
  24.     vector<Node> T;
  25. public:
  26.     DynTree() {
  27.         T.push_back(Node(0, INT_MAX));
  28.     }
  29.  
  30.     void Update(int v, int pos, int delta);
  31.     long long Get(int v, int pos) const;
  32. };
  33.  
  34. void DynTree::Update(int v, int pos, int delta) {
  35.     T[v].cnt += delta;
  36.     if (T[v].tl == T[v].tr) {
  37.         return;
  38.     }
  39.    
  40.     const int tm = (T[v].tl + T[v].tr) >> 1;
  41.     if (T[v].left == -1 && pos <= tm) {
  42.         T.push_back(Node(T[v].tl, tm));
  43.         T[v].left = T.size() - 1;
  44.     }
  45.     if (pos <= tm) {
  46.         Update(T[v].left, pos, delta);
  47.     }
  48.    
  49.  
  50.     if (T[v].right == -1 && pos > tm) {
  51.         T.push_back(Node(tm + 1, T[v].tr));
  52.         T[v].right = T.size() - 1;
  53.     }
  54.     if (pos > tm) {
  55.         Update(T[v].right, pos, delta);
  56.     }
  57. }
  58.  
  59. long long DynTree::Get(int v, int pos) const {
  60.     if (pos == T[v].tl) {
  61.         return T[v].cnt;
  62.     }
  63.     const int tm = (T[v].tl + T[v].tr) >> 1;
  64.     long long ans = 0;
  65.     if (pos <= tm) {
  66.         if (T[v].left != -1) {
  67.             ans += Get(T[v].left, pos);
  68.         }
  69.         if (T[v].right != -1) {
  70.             ans += Get(T[v].right, tm + 1);
  71.         }
  72.     }
  73.     else{
  74.         if (T[v].right != -1) {
  75.             ans += Get(T[v].right, pos);
  76.         }
  77.     }
  78.     return ans;
  79. }
  80.  
  81. bool cmp(std::pair<int, int> p1, std::pair<int, int> p2){
  82.     if ((p1.first < p2.first) || (p1.first == p2.first && p1.second > p2.second)) {
  83.         return true;
  84.     }
  85.     return false;
  86. }
  87.  
  88. int main(){
  89.     std::ios_base::sync_with_stdio(false);
  90.     cin.tie(nullptr);
  91.     cout.tie(nullptr);
  92.    
  93.     int n;
  94.     cin >> n;
  95.     vector<pair<int, int>> segments(n);
  96.     int left, right;
  97.     for (int i = 0; i < n; ++i) {
  98.         std::cin >> left >> right;
  99.         segments[i] = {left, right};
  100.     }
  101.    
  102.     sort(segments.begin(), segments.end(), cmp);
  103.     DynTree tree;
  104.    
  105.     long long ans = 0;
  106.     int cnt = 0;
  107.     int pleft = segments[0].first, pright = segments[0].second;
  108.    
  109.     for (int i = 0; i < segments.size(); ++i) {
  110.         if (segments[i].first == pleft && segments[i].second == pright) {
  111.             ++cnt;
  112.         }
  113.         else {
  114.             tree.Update(0, pright, cnt);
  115.             cnt = 1;
  116.             pleft = segments[i].first;
  117.             pright = segments[i].second;
  118.         }
  119.         ans += tree.Get(0, segments[i].second);
  120.     }
  121.     cout << ans;
  122.    
  123.     return 0;
  124. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement