Advertisement
Guest User

Untitled

a guest
Aug 20th, 2015
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.92 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #include <algorithm>
  5. #include <math.h>
  6. #include <set>
  7. #include <map>
  8. #include <vector>
  9. #include <sstream>
  10. #include <queue>
  11. #include <unordered_map>
  12. #include <stack>
  13. #define lol long long
  14. using namespace std;
  15.  
  16.  
  17. class LenivoeDO
  18. {
  19.     struct Node
  20.     {
  21.         Node * left;
  22.         Node * right;
  23.         int val;
  24.         Node()
  25.         {
  26.             left = right = 0;
  27.             val = 0;
  28.         }
  29.  
  30.     };
  31.     Node * head;
  32. public:
  33.     LenivoeDO()
  34.     {
  35.         head = new Node();
  36.         head->val = 0;
  37.         head->left = head->right = 0;
  38.     }
  39. private:
  40.     void update(Node * curr, int tl, int tr, int x, int val)
  41.     {
  42.         if (tl > tr)
  43.             return;
  44.         if (tl == tr)
  45.         {
  46.             curr->val += val;
  47.             return;
  48.         }
  49.         int m = (tl + tr) / 2;
  50.         if (x <= m)
  51.         {
  52.             if (!curr->left)
  53.                 curr->left = new Node();
  54.             update(curr->left, tl, m, x, val);
  55.         }
  56.         else
  57.         {
  58.             if (!curr->right)
  59.                 curr->right = new Node();
  60.             update(curr->right, m + 1, tr, x, val);
  61.         }
  62.         curr->val = (curr->left ? curr->left->val : 0) + (curr->right ? curr->right->val : 0);
  63.     }
  64.  
  65.     int sum(Node * curr, int tl, int tr, int l, int r)
  66.     {
  67.         if (curr == 0)
  68.             return 0;
  69.         if (tl > tr)
  70.             return 0;
  71.         if (tl == l && tr == r)
  72.         {
  73.             return curr->val;
  74.         }
  75.         int m = (tl + tr) / 2;
  76.         return sum(curr->left, tl, m, l, min(m, r)) +
  77.             sum(curr->right, m + 1, tr, max(l, m + 1), r);
  78.     }
  79. public:
  80.     void addPlease(int ind, int add)
  81.     {
  82.         update(head, 0, 1e9 + 228, ind, add);
  83.     }
  84.     int skolkoBudet(int l, int r)
  85.     {
  86.         return sum(head, 0, 1e9 + 228, max(0, l), r);
  87.     }
  88. };
  89.  
  90. int main()
  91. {
  92.     ios_base::sync_with_stdio(0);
  93.     cin.tie(0);
  94.    
  95.     int n, m, l;
  96.     cin >> n >> m >> l;
  97.  
  98.     map<int, vector<vector<int>>> a;
  99.     for (int i = 0; i < n + m; ++i)
  100.     {
  101.         int x, y;
  102.         cin >> x >> y;
  103.         if (a.find(x) == a.end())
  104.             a[x] = vector<vector<int>>(3);
  105.         a[x][i >= n].push_back(y);
  106.         if (i >= n)
  107.             continue;
  108.         if (x + l <= 1000000005)
  109.         {
  110.             if (a.find(x + l) == a.end())
  111.                 a[x + l] = vector<vector<int>>(3);
  112.             a[x + l][2].push_back(y);
  113.         }
  114.     }
  115.     LenivoeDO rammstein;
  116.     int best = 0;
  117.     for (auto it : a)
  118.     {
  119.         for (auto it2 : it.second[0])
  120.             rammstein.addPlease(it2, 1);
  121.        
  122.         for (auto it2 : it.second[1])
  123.         {
  124.             int ans2 = rammstein.skolkoBudet(it2 - l, it2);
  125.             best = max(best, ans2);
  126.         }
  127.        
  128.         for (auto it2 : it.second[2])
  129.             rammstein.addPlease(it2, -1);
  130.     }
  131.  
  132.     cout << best << endl;
  133. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement