Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <string>
- #include <algorithm>
- #include <math.h>
- #include <set>
- #include <map>
- #include <vector>
- #include <sstream>
- #include <queue>
- #include <unordered_map>
- #include <stack>
- #define lol long long
- using namespace std;
- class LenivoeDO
- {
- struct Node
- {
- Node * left;
- Node * right;
- int val;
- Node()
- {
- left = right = 0;
- val = 0;
- }
- };
- Node * head;
- public:
- LenivoeDO()
- {
- head = new Node();
- head->val = 0;
- head->left = head->right = 0;
- }
- private:
- void update(Node * curr, int tl, int tr, int x, int val)
- {
- if (tl > tr)
- return;
- if (tl == tr)
- {
- curr->val += val;
- return;
- }
- int m = (tl + tr) / 2;
- if (x <= m)
- {
- if (!curr->left)
- curr->left = new Node();
- update(curr->left, tl, m, x, val);
- }
- else
- {
- if (!curr->right)
- curr->right = new Node();
- update(curr->right, m + 1, tr, x, val);
- }
- curr->val = (curr->left ? curr->left->val : 0) + (curr->right ? curr->right->val : 0);
- }
- int sum(Node * curr, int tl, int tr, int l, int r)
- {
- if (curr == 0)
- return 0;
- if (tl > tr)
- return 0;
- if (tl == l && tr == r)
- {
- return curr->val;
- }
- int m = (tl + tr) / 2;
- return sum(curr->left, tl, m, l, min(m, r)) +
- sum(curr->right, m + 1, tr, max(l, m + 1), r);
- }
- public:
- void addPlease(int ind, int add)
- {
- update(head, 0, 1e9 + 228, ind, add);
- }
- int skolkoBudet(int l, int r)
- {
- return sum(head, 0, 1e9 + 228, max(0, l), r);
- }
- };
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- int n, m, l;
- cin >> n >> m >> l;
- map<int, vector<vector<int>>> a;
- for (int i = 0; i < n + m; ++i)
- {
- int x, y;
- cin >> x >> y;
- if (a.find(x) == a.end())
- a[x] = vector<vector<int>>(3);
- a[x][i >= n].push_back(y);
- if (i >= n)
- continue;
- if (x + l <= 1000000005)
- {
- if (a.find(x + l) == a.end())
- a[x + l] = vector<vector<int>>(3);
- a[x + l][2].push_back(y);
- }
- }
- LenivoeDO rammstein;
- int best = 0;
- for (auto it : a)
- {
- for (auto it2 : it.second[0])
- rammstein.addPlease(it2, 1);
- for (auto it2 : it.second[1])
- {
- int ans2 = rammstein.skolkoBudet(it2 - l, it2);
- best = max(best, ans2);
- }
- for (auto it2 : it.second[2])
- rammstein.addPlease(it2, -1);
- }
- cout << best << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement