271 2021. 06. 22 14:56:29 mraron Hadjárat cpp14 Elfogadva 100/100 101ms 5416 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;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 100/100
1 Elfogadva 0/0 2ms 1756 KiB
2 Elfogadva 0/0 41ms 3668 KiB
3 Elfogadva 4/4 1ms 1848 KiB
4 Elfogadva 4/4 1ms 1856 KiB
5 Elfogadva 4/4 1ms 1852 KiB
6 Elfogadva 4/4 1ms 1860 KiB
7 Elfogadva 4/4 1ms 1848 KiB
8 Elfogadva 4/4 1ms 1852 KiB
9 Elfogadva 4/4 1ms 1864 KiB
10 Elfogadva 4/4 1ms 1888 KiB
11 Elfogadva 4/4 4ms 2116 KiB
12 Elfogadva 4/4 8ms 2212 KiB
13 Elfogadva 6/6 8ms 2212 KiB
14 Elfogadva 6/6 14ms 2560 KiB
15 Elfogadva 6/6 21ms 3080 KiB
16 Elfogadva 6/6 43ms 3596 KiB
17 Elfogadva 6/6 50ms 4116 KiB
18 Elfogadva 6/6 59ms 4248 KiB
19 Elfogadva 6/6 71ms 4764 KiB
20 Elfogadva 6/6 89ms 5416 KiB
21 Elfogadva 6/6 101ms 5412 KiB
22 Elfogadva 6/6 93ms 5288 KiB