Advertisement
Guest User

Untitled

a guest
Mar 21st, 2019
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 140005;
  5.  
  6. int i, j, k, h, w, n, rs, x, y, ans[4 * N], totalSum[4 * N];
  7. pair<int, int> a[N];
  8.  
  9. int goToNext(int x, int i) {
  10.   for(++i; i <= n && a[i].first == x; ++i);
  11.   return i;
  12. }
  13.  
  14. void update(int left, int right, int nod) {
  15.   if(left == right) {
  16.     totalSum[nod] += y;
  17.     ans[nod] = totalSum[nod];
  18.   } else {
  19.     int pivot = (left + right) / 2;
  20.     if(x <= pivot) update(left, pivot, 2 * nod);
  21.     else update(pivot + 1, right, 2 * nod + 1);
  22.     totalSum[nod] = totalSum[2 * nod] + totalSum[2 * nod + 1];
  23.     ans[nod] = max(ans[2 * nod], totalSum[2 * nod] + ans[2 * nod + 1]);
  24.   }
  25. }
  26.  
  27. int main() {
  28.   freopen("mine.in", "r", stdin);
  29.   freopen("mine.out", "w", stdout);
  30.  
  31.   scanf("%d %d %d", &h, &w, &n);
  32.   for(i = 1; i <= n; ++i) scanf("%d %d", &a[i].first, &a[i].second), a[i].first += 30001, a[i].second += 30001;
  33.  
  34.   sort(a + 1, a + n + 1);
  35.  
  36.   for(j = i = 1; i <= n; ++i) {
  37.     x = 2 * a[i].second - 1; y = 1; update(1, N - 1, 1);
  38.     x = 2 * (a[i].second + w); y = -1; update(1, N - 1, 1);
  39.     while(a[i].first - a[j].first > h) {
  40.       x = 2 * a[j].second - 1; y = -1; update(1, N - 1, 1);
  41.       x = 2 * (a[j].second + w); y = 1; update(1, N - 1, 1);
  42.       ++j;
  43.     }
  44.     rs = max(rs, ans[1]);
  45.   }
  46.  
  47.   printf("%d\n", rs);
  48.  
  49.   return 0;
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement