2712021-06-22 14:56:29mraronHadjáratcpp14Accepted 100/100101ms5416 KiB
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using namespace std;

struct pont {
  int x, y, id;

  bool operator<(const pont& p) const {
    return x < p.x || (x == p.x && y < p.y);
  }
};

// best[i]: i hosszú sorozatok legjobb végződései
vector<set<pont>> best(1, set<pont>({{-1, -1, 0}}));

// Van-e olyan k hosszú, aminek a végére lehet tenni a p-t, ha van akkor id-t ad vissza.
int extends(int k, pont p) {
  auto it = best[k].lower_bound({p.x, -1, -1});
  if (it == best[k].begin()) return -1;
  --it;
  if (it->y < p.y) return it->id;
  return -1;
}

// Mi a leghosszabb, aminek a végére lehet tenni a p-t
int search_longest_extendable(pont p) {
  int l = 0, r = best.size();
  while (l + 1 < r) {
    int mid = (l + r) / 2;
    if (extends(mid, p) >= 0) l = mid;
    else r = mid;
  }
  return l;
}

// A best[k] -ba beszúrjuk p-t
void improve(int k, pont p) {
  if (size_t(k) >= best.size()) {
    best.push_back(set<pont>({p}));
    return;
  }
  auto it = best[k].lower_bound(p);
  if (it != best[k].begin()) {
    auto prev = it;
    --prev;
    if (prev->x == p.x || prev->y == p.y) {
      // van a p-nél jobb már bent
      return;
    }
  }
  it = best[k].insert(it, p);
  ++it;
  while (it != best[k].end() && it->y >= p.y) {
    it = best[k].erase(it);
  }
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;

  vector<pont> v(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> v[i].x >> v[i].y;
    v[i].id = i;
  }
  v[0] = {-1, -1, 0};

  vector<int> prev(n + 1);
  for (int i = 1; i <= n; i++) {
    int k = search_longest_extendable(v[i]);
    prev[i] = extends(k, v[i]);
    improve(k + 1, v[i]);
  }
  cout << best.size() - 1 << endl;

  int m = best.back().begin()->id;
  vector<int> sol;
  while (m != 0) {
    sol.push_back(m);
    m = prev[m];
  }
  reverse(sol.begin(), sol.end());
  for (int x : sol) cout << x << " ";
  cout << endl;
  return 0;
}
SubtaskSumTestVerdictTimeMemory
base100/100
1Accepted0/02ms1756 KiB
2Accepted0/041ms3668 KiB
3Accepted4/41ms1848 KiB
4Accepted4/41ms1856 KiB
5Accepted4/41ms1852 KiB
6Accepted4/41ms1860 KiB
7Accepted4/41ms1848 KiB
8Accepted4/41ms1852 KiB
9Accepted4/41ms1864 KiB
10Accepted4/41ms1888 KiB
11Accepted4/44ms2116 KiB
12Accepted4/48ms2212 KiB
13Accepted6/68ms2212 KiB
14Accepted6/614ms2560 KiB
15Accepted6/621ms3080 KiB
16Accepted6/643ms3596 KiB
17Accepted6/650ms4116 KiB
18Accepted6/659ms4248 KiB
19Accepted6/671ms4764 KiB
20Accepted6/689ms5416 KiB
21Accepted6/6101ms5412 KiB
22Accepted6/693ms5288 KiB