Manhattan Mornings

#include <bits/stdc++.h>
#define ll long long

using namespace std;

typedef long double ld;
//typedef pair<ll, ll> P;
struct P {
  ll first, second;
  int i;
};
bool operator<(const P &a, const P &b) {
  return tie(a.first, a.second, a.i) < tie(b.first, b.second, b.i);
}


bool ysort(const P &a, const P &b) {
  if (a.second != b.second) return a.second < b.second;
  return a.first < b.first;
}

int main() {
  int n;
  cin >> n;
  ll x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;

  vector<P> xdir, ydir;

  for (int i = 0; i < n; i++) {
    ll x, y;
    cin >> x >> y;
    xdir.push_back(P{x, y, i});
    ydir.push_back(P{x, y, i});
  }

  if (x1 > x2) {
    for (int i = 0; i < n; i++) {
      xdir[i].first *= -1;
      ydir[i].first *= -1;
    }
    x1 *= -1;
    x2 *= -1;
  }
  if (y1 > y2) {
    for (int i = 0; i < n; i++) {
      xdir[i].second *= -1;
      ydir[i].second *= -1;
    }
    y1 *= -1;
    y2 *= -1;
  }

  sort(xdir.begin(), xdir.end());
  sort(ydir.begin(), ydir.end(), ysort);

  map<P, int> xi;
  map<P, int> yi;

  for (int i = 0; i < n; i++) xi[xdir[i]] = i;
  for (int i = 0; i < n; i++) yi[ydir[i]] = i;

  map<P, int> dyn;

  //cerr<<"p1 "<<x1<<" "<<y1<<endl;
  //cerr<<"p2 "<<x2<<" "<<y2<<endl;
  for (int i = 0; i < n; i++) {
    P cur = xdir[i];
    //cerr << "at " << cur.first << " "<<cur.second<<endl;
    if (cur.first < x1) continue;
    if (cur.second < y1) continue;

    int xj = xi[cur];
    int yj = yi[cur];
    int res = 1;
    if (i > 0) {
      if (xdir[xj-1].second <= cur.second) {
        res = max(res, 1+dyn[xdir[xj-1]]);
      }
    }
    if (yj > 0) {
      if (ydir[yj-1].first <= cur.first) {
        res = max(res, 1+dyn[ydir[yj-1]]);
      }
    }

    dyn[cur] = res;
  }

  //for (auto f : dyn)
    //cerr << f.first.first << ", " << f.first.second << ": " << f.second << endl;

  int best = 0;
  for (int i = 0; i < n; i++) {
    P cur = xdir[i];
    if (cur.first > x2) continue;
    if (cur.second > y2) continue;
    best = max(best, dyn[cur]);
  }

  cout << best << endl;

  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: ACCEPTED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: WRONG ANSWER

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: WRONG ANSWER

Test 31

Verdict: WRONG ANSWER

Test 32

Verdict: ACCEPTED

Test 33

Verdict: WRONG ANSWER

Test 34

Verdict: WRONG ANSWER

Test 35

Verdict: WRONG ANSWER

Test 36

Verdict: WRONG ANSWER

Test 37

Verdict: WRONG ANSWER

Test 38

Verdict: WRONG ANSWER

Test 39

Verdict: WRONG ANSWER

Test 40

Verdict: WRONG ANSWER

Test 41

Verdict: WRONG ANSWER

Test 42

Verdict: WRONG ANSWER

Test 43

Verdict: WRONG ANSWER