Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll MAXN = 1e5;
- ll n, v;
- ll plx[MAXN], ply[MAXN], mly[MAXN];
- void cqsort(ll a, ll b){
- ll m = plx[(a + b) >> 1],
- i = a, j = b;
- do {
- while (plx[i] > m){
- ++i;
- }
- while (plx[j] < m){
- --j;
- }
- if (i <= j){
- swap(plx[i], plx[j]);
- swap(ply[i], ply[j]);
- ++i;
- --j;
- }
- } while (i < j);
- if (j > a){
- cqsort(a, j);
- }
- if (i < b){
- cqsort(i, b);
- }
- }
- void ctr(ll &x, ll &y){
- ll _x = x;
- x -= y * v;
- y = _x * 2 - x;
- }
- ll tree[4 * MAXN];
- void tupdate(ll pos, ll val, ll tl, ll tr, ll v){
- if (tl == tr){
- tree[v] = val;
- } else {
- ll tm = (tl + tr) >> 1;
- if (pos <= tm){
- tupdate(pos, val, tl, tm, (v << 1) + 1);
- } else {
- tupdate(pos, val, tm + 1, tr, (v << 1) + 2);
- }
- tree[v] = max(tree[(v << 1) + 1], tree[(v << 1) + 2]);
- }
- }
- ll tget(ll l, ll r, ll tl, ll tr, ll v){
- if (l > r){
- return 0;
- } else {
- if (l == tl && r == tr){
- return tree[v];
- }
- ll tm = (tl + tr) >> 1;
- return max(tget(l, min(tm, r), tl, tm, (v << 1) + 1),
- tget(max(tm + 1, l), r, tm + 1, tr, (v << 1) + 2));
- }
- }
- int main(){
- freopen("input.txt", "r", stdin);
- cin >> n;
- for (ll l(0); l < n; ++l){
- cin >> plx[l] >> ply[l];
- }
- cin >> v;
- for (ll l(0); l < n; ++l){
- ctr(plx[l], ply[l]);
- mly[l] = ply[l];
- }
- cqsort(0, n - 1);
- sort(mly, mly + n);
- for (ll l(0); l < MAXN; ++l){
- tree[l] = 0;
- }
- ll _max = 0;
- for (ll l(0); l < n; ++l){
- if (plx[l] > 0 || ply[l] < 0){
- continue;
- }
- ll yv = ply[l];
- ll pos = distance(mly, lower_bound(mly, mly + n, yv));
- ll maxn = tget(0, pos, 0, n - 1, 0);
- tupdate(pos, maxn + 1, 0, n - 1, 0);
- _max = max(_max, maxn);
- }
- cout << _max + 1 << " ";
- for (ll l(0); l < MAXN; ++l){
- tree[l] = 0;
- }
- _max = 0;
- for (ll l(0); l < n; ++l){
- ll yv = ply[l];
- ll pos = distance(mly, lower_bound(mly, mly + n, yv));
- ll maxn = tget(0, pos, 0, n - 1, 0);
- tupdate(pos, maxn + 1, 0, n - 1, 0);
- _max = max(_max, maxn);
- }
- cout << _max + 1;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement