233872026-01-21 12:56:24algoproHadjáratcpp17Elfogadva 100/100115ms3640 KiB
// UUID: c29a5653-0e2d-4d22-a4bc-d80e72d67d8f
#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});
  if (it == best[k].begin()) return -1;
  return (--it)->y < p.y ? it->id : -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 (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ÖsszpontTesztVerdiktIdőMemória
base100/100
1Elfogadva0/01ms316 KiB
2Elfogadva0/052ms1332 KiB
3Elfogadva4/41ms316 KiB
4Elfogadva4/41ms316 KiB
5Elfogadva4/41ms316 KiB
6Elfogadva4/41ms368 KiB
7Elfogadva4/41ms316 KiB
8Elfogadva4/41ms316 KiB
9Elfogadva4/41ms316 KiB
10Elfogadva4/42ms316 KiB
11Elfogadva4/44ms564 KiB
12Elfogadva4/49ms744 KiB
13Elfogadva6/69ms728 KiB
14Elfogadva6/618ms820 KiB
15Elfogadva6/629ms1344 KiB
16Elfogadva6/652ms1848 KiB
17Elfogadva6/664ms2180 KiB
18Elfogadva6/675ms2648 KiB
19Elfogadva6/689ms3024 KiB
20Elfogadva6/6115ms3640 KiB
21Elfogadva6/6114ms3632 KiB
22Elfogadva6/6114ms3640 KiB