fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef pair<int, int> PII;
  5.  
  6. const int MAX_N = 15005;
  7. const int SHIFT = 30001;
  8.  
  9. PII a[MAX_N];
  10.  
  11. const int MAX_LEAVES = 2 * SHIFT + 5;
  12.  
  13. int T[4*MAX_LEAVES], lazy[4*MAX_LEAVES];
  14.  
  15. void push(int v) {
  16.     T[2*v] += lazy[v];
  17.     T[2*v+1] += lazy[v];
  18.     lazy[2*v+1] += lazy[v];
  19.     lazy[2*v+1] += lazy[v];
  20.     lazy[v] = 0;
  21. }
  22.  
  23. void update(int v, int l, int r, int qL, int qR, int val) {
  24.     if (l > qR || r < qL) return;
  25.  
  26.     if (qL <= l && r <= qR) {
  27.         T[v] += val;
  28.         lazy[v] += val;
  29.         return;
  30.     }
  31.  
  32.     int mid = (l + r) / 2;
  33.     push(v);
  34.     update(2*v, l, mid, qL, qR, val);
  35.     update(2*v+1, mid+1, r, qL, qR, val);
  36.  
  37.     T[v] = max(T[2*v], T[2*v+1]);
  38. }
  39.  
  40. int query(int v, int l, int r, int qL, int qR) {
  41.     if (l > qR || r < qL) return 0;
  42.  
  43.     if (qL <= l && r <= qR) return T[v];
  44.  
  45.     int mid = (l + r) / 2;
  46.     push(v);
  47.  
  48.     return max(query(2*v, l, mid, qL, qR), query(2*v+1, mid+1, r, qL, qR));
  49. }
  50.  
  51. int main() {
  52.  
  53.     int S, W, n;
  54.     cin >> S >> W >> n;
  55.  
  56.     for (int i = 0; i < n; i++) {
  57.         cin >> a[i].first >> a[i].second;
  58.         a[i].second += SHIFT;
  59.     }
  60.  
  61.     sort(a, a+n);
  62.  
  63.     int last_removed = 0;
  64.     int ans = 0;
  65.  
  66.     for (int i = 0; i < n; i++) {
  67.         int bottom = max(1, a[i].second - W);
  68.         update(1, 1, 2*SHIFT, bottom, a[i].second, 1);
  69.  
  70.         while (last_removed < n && a[last_removed].first < a[i].first - S) {
  71.             int new_bottom = max(1, a[last_removed].second - W);
  72.             update(1, 1, 2*SHIFT, new_bottom, a[last_removed].second, -1);
  73.             last_removed++;
  74.         }
  75.  
  76.         ans = max(ans, query(1, 1, 2*SHIFT, bottom, a[i].second));
  77.     }
  78.  
  79.     cout << ans;
  80.  
  81.  
  82.     return 0;
  83. }
  84.  
Success #stdin #stdout 0.01s 5500KB
comments (?)
stdin
copy 
1 2
12
0 0
1 1
2 2
3 3
4 5
5 5
4 2
1 4
0 5
5 0
2 3
3 2
stdout
copy 
4
https://ideone.com/xwvhWL
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!