• API
• FAQ
• Tools
• Archive
daily pastebin goal
82%
SHARE
TWEET

# Untitled

a guest Mar 21st, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top