Advertisement
Na2a

Untitled

Aug 20th, 2015
282
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define pii pair<int, int>
  6.  
  7. #define pb push_back
  8. #define mp make_pair
  9.  
  10. #define f first
  11. #define s second
  12.  
  13. using namespace __gnu_pbds;
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17.  
  18. const int INF = (int) 1e9 + 7;
  19. const int MAXN = (int) 1e6 + 7;
  20.  
  21. typedef
  22. tree<
  23.   pii,
  24.   null_type,
  25.   less<pii>,
  26.   rb_tree_tag,
  27.   tree_order_statistics_node_update>
  28. ordered_set;
  29.  
  30. int n, m, len;
  31.  
  32. pii p[MAXN];
  33. pii q[MAXN];
  34.  
  35. int main() {
  36.   #ifdef LOCAL
  37.   freopen("in", "r", stdin);
  38.   #endif
  39.  
  40.   scanf("%d%d%d", &n, &m, &len);
  41.   for (int i = 1; i <= n; i++)
  42.     scanf("%d%d", &p[i].f, &p[i].s);
  43.   for (int i = 1; i <= m; i++)
  44.     scanf("%d%d", &q[i].f, &q[i].s);
  45.  
  46.   sort(p + 1, p + n + 1);
  47.   sort(q + 1, q + m + 1);
  48.  
  49.   int l = 1, r = 1;
  50.   int ans = 0;
  51.   ordered_set all;
  52.   for (int i = 1; i <= m; i++) {
  53.     while (r <= n && p[r].f <= q[i].f) {
  54.       all.insert(mp(p[r].s, r));
  55.       r++;
  56.     }
  57.     while (l <= n && p[l].f + len < q[i].f) {
  58.       all.erase(mp(p[l].s, l));
  59.       l++;
  60.     }
  61.     int total = all.order_of_key(mp(q[i].s, INF));
  62.     int bad = all.order_of_key(mp(q[i].s - len, -INF));
  63.     ans = max(ans, total - bad);
  64.   }
  65.   cout << ans;
  66.  
  67.   return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement