Advertisement
Guest User

Untitled

a guest
Mar 27th, 2017
43
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.58 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6.  
  7. const ll MAXN = 1e5;
  8.  
  9. ll n, v;
  10. ll plx[MAXN], ply[MAXN], mly[MAXN];
  11.  
  12. void cqsort(ll a, ll b){
  13.  
  14.     ll m = plx[(a + b) >> 1],
  15.         i = a, j = b;
  16.  
  17.     do {
  18.  
  19.         while (plx[i] > m){
  20.             ++i;
  21.         }
  22.         while (plx[j] < m){
  23.             --j;
  24.         }
  25.  
  26.         if (i <= j){
  27.             swap(plx[i], plx[j]);
  28.             swap(ply[i], ply[j]);
  29.             ++i;
  30.             --j;
  31.         }
  32.  
  33.     } while (i < j);
  34.  
  35.     if (j > a){
  36.         cqsort(a, j);
  37.     }
  38.     if (i < b){
  39.         cqsort(i, b);
  40.     }
  41.  
  42. }
  43.  
  44. void ctr(ll &x, ll &y){
  45.  
  46.     ll _x = x;
  47.  
  48.     x -= y * v;
  49.     y = _x * 2 - x;
  50.  
  51. }
  52.  
  53. ll tree[4 * MAXN];
  54.  
  55. void tupdate(ll pos, ll val, ll tl, ll tr, ll v){
  56.  
  57.     if (tl == tr){
  58.         tree[v] = val;
  59.     } else {
  60.  
  61.         ll tm = (tl + tr) >> 1;
  62.  
  63.         if (pos <= tm){
  64.             tupdate(pos, val, tl, tm, (v << 1) + 1);
  65.         } else {
  66.             tupdate(pos, val, tm + 1, tr, (v << 1) + 2);
  67.         }
  68.  
  69.         tree[v] = max(tree[(v << 1) + 1], tree[(v << 1) + 2]);
  70.  
  71.     }
  72.  
  73. }
  74.  
  75. ll tget(ll l, ll r, ll tl, ll tr, ll v){
  76.  
  77.     if (l > r){
  78.         return 0;
  79.     } else {
  80.  
  81.         if (l == tl && r == tr){
  82.             return tree[v];
  83.         }
  84.  
  85.         ll tm = (tl + tr) >> 1;
  86.  
  87.         return max(tget(l, min(tm, r), tl, tm, (v << 1) + 1),
  88.                    tget(max(tm + 1, l), r, tm + 1, tr, (v << 1) + 2));
  89.  
  90.     }
  91.  
  92. }
  93.  
  94. int main(){
  95.  
  96.     freopen("input.txt", "r", stdin);
  97.  
  98.     cin >> n;
  99.  
  100.     for (ll l(0); l < n; ++l){
  101.         cin >> plx[l] >> ply[l];
  102.     }
  103.  
  104.     cin >> v;
  105.  
  106.     for (ll l(0); l < n; ++l){
  107.         ctr(plx[l], ply[l]);
  108.         mly[l] = ply[l];
  109.     }
  110.  
  111.     cqsort(0, n - 1);
  112.     sort(mly, mly + n);
  113.  
  114.     for (ll l(0); l < MAXN; ++l){
  115.         tree[l] = 0;
  116.     }
  117.  
  118.     ll _max = 0;
  119.  
  120.     for (ll l(0); l < n; ++l){
  121.  
  122.         if (plx[l] > 0 || ply[l] < 0){
  123.             continue;
  124.         }
  125.  
  126.         ll yv = ply[l];
  127.         ll pos = distance(mly, lower_bound(mly, mly + n, yv));
  128.  
  129.         ll maxn = tget(0, pos, 0, n - 1, 0);
  130.         tupdate(pos, maxn + 1, 0, n - 1, 0);
  131.  
  132.         _max = max(_max, maxn);
  133.  
  134.     }
  135.  
  136.     cout << _max + 1 << " ";
  137.  
  138.     for (ll l(0); l < MAXN; ++l){
  139.         tree[l] = 0;
  140.     }
  141.  
  142.     _max = 0;
  143.  
  144.     for (ll l(0); l < n; ++l){
  145.  
  146.         ll yv = ply[l];
  147.         ll pos = distance(mly, lower_bound(mly, mly + n, yv));
  148.  
  149.         ll maxn = tget(0, pos, 0, n - 1, 0);
  150.         tupdate(pos, maxn + 1, 0, n - 1, 0);
  151.  
  152.         _max = max(_max, maxn);
  153.  
  154.     }
  155.  
  156.     cout << _max + 1;
  157.  
  158. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement