49692023-04-08 00:08:39TomaSajtHadjáratcpp17Accepted 100/10097ms5248 KiB
#include <bits/stdc++.h>
using namespace std;
// this solution was made using mraron's solution as a reference (on njudge)

struct point {
  int x, y, id;
  bool operator<(const point &p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
};

// `best[i]` is the best endings for series of length `i`
// we always make sure that inside `best[i]`
// every `.x` is unique and is in increasing order
// every `.y` is unique and is in decreasing order
// we try to minimize `.y` as much as possible
vector<set<point>> best(1, {{-1, -1, 0}});

// Is there a series of length `k` which could be extended to using `p`
// If there is, returns the `.id` of the last element of the series
// If not, returns -1
int extends(int k, point p) {
  auto it = best[k].lower_bound({p.x, -1, -1});
  if (it == best[k].begin()) // there are no smaller x values in best[k]
    return -1;
  --it;
  // is now guaranteed that it->x < p.x
  // we know that no other point has it->x for value x other than *it
  // so there's no need to go lower than --it
  if (it->y < p.y)
    return it->id;
  return -1;
}

// what is the longest series which could be extended by `p`
// returns the length of the series and the `.id` of the last element
pair<int, int> get_longest_extension(point p) {
  int l = 0, r = best.size();
  int id = 0;
  while (l + 1 < r) {
    int mid = (l + r) / 2;
    int res = extends(mid, p);
    if (res != -1) {
      l = mid;
      id = res;
    } else {
      r = mid;
    }
  }
  return {l, id};
}

// tries to insert `p` into `best[k]` while ensuring the two-way sort order
void insert_and_prune(int k, point p) {
  if (k >= best.size()) {
    best.push_back({p});
    return;
  }
  auto it = best[k].lower_bound(p);

  // if not the first in the sort order
  if (it != best[k].begin()) {
    auto p_it = std::prev(it);
    // if the two-way sorted structure would be broken, don't insert
    if (p_it->x == p.x || p_it->y == p.y)
      return;
  }
  it = best[k].insert(it, p);
  ++it;
  // ensure decreasing `.y` values
  while (it != best[k].end() && it->y >= p.y) {
    it = best[k].erase(it);
  }
}

int main() {
  cin.tie(0), ios::sync_with_stdio(0);
  int n;
  cin >> n;

  vector<int> prev(n + 1);
  for (int i = 1; i <= n; i++) {
    point p;
    cin >> p.x >> p.y;
    p.id = i;
    auto [k, pi] = get_longest_extension(p);
    prev[i] = pi;
    insert_and_prune(k + 1, p);
  }

  int curr = best.back().begin()->id;
  stack<int> res;
  while (curr != 0) {
    res.push(curr);
    curr = prev[curr];
  }
  cout << res.size() << '\n';
  while (!res.empty()) {
    cout << res.top() << ' ';
    res.pop();
  }
  return 0;
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/03ms1892 KiB
2Accepted0/045ms2928 KiB
3Accepted4/43ms2296 KiB
4Accepted4/43ms2512 KiB
5Accepted4/43ms2608 KiB
6Accepted4/43ms2600 KiB
7Accepted4/43ms2732 KiB
8Accepted4/43ms2944 KiB
9Accepted4/43ms3036 KiB
10Accepted4/43ms3188 KiB
11Accepted4/46ms3292 KiB
12Accepted4/49ms3452 KiB
13Accepted6/69ms3732 KiB
14Accepted6/617ms3880 KiB
15Accepted6/626ms4048 KiB
16Accepted6/645ms4292 KiB
17Accepted6/656ms4364 KiB
18Accepted6/665ms4672 KiB
19Accepted6/675ms4888 KiB
20Accepted6/697ms5232 KiB
21Accepted6/697ms5248 KiB
22Accepted6/697ms5248 KiB