提出 #66777575

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<typename T>
ostream& operator<<(ostream &o, vector<T> v) {
  for (int i = 0; i < v.size(); i++)
    o << v[i] << (i+1<v.size()?" ":"");
  return o;
}

const int iinf = 1e9+7;
const ll inf = 1e18+7;

using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;

template <typename T>
struct SegTree {
  using F = function<T(T, T)>;
  int n;
  F f;
  T ti;
  vector<T> dat;
  SegTree() {}
  SegTree(F f, T ti,unsigned int num) : f(f), ti(ti) {
    n = max(int(__bit_ceil(num)), 1);
    dat.assign(n << 1, ti);
  }
  SegTree(F f,T ti,vector<T>&v):SegTree(f,ti,v.size()){
    for (int i = 0; i < v.size(); i++)
      dat[n + i] = v[i];
    for(int i=n-1;i;i--) dat[i]=f(dat[i*2], dat[i*2+1]);
  }
  void set_val(int k, T x) {
    k += n;
    dat[k] = f(dat[k], x);
    while(k >>= 1) dat[k] = f(dat[k*2], dat[k*2+1]);
  }
  T query(int a, int b) {
    if (a >= b) return ti;
    T vl = ti, vr = ti;
    for (int l=a+n, r=b+n; l<r; l>>=1, r>>=1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(false);
  int n;
  cin >> n;
  vector<pll> ab(n);
  for (int i = 0; i < n; i++) {
    cin >> ab[i].first >> ab[i].second;
    ab[i].first--;
    ab[i].second--;
    if (ab[i].first > ab[i].second) swap(ab[i].first, ab[i].second);
  }
  for (int i = 0; i < n; i++) {
    ab.emplace_back(ab[i].first+2*n, ab[i].second+2*n);
    ab.emplace_back(ab[i].second, ab[i].first+2*n);
  }
  SegTree<ll> seg([&](ll a, ll b) { return max(a, b); }, 0LL, n*4);
  sort(ab.begin(), ab.end(), [&](auto a, auto b) {
    if (a.first == b.first) {
      return a.second < b.second;
    } else {
      return a.first > b.first;
    }
  });
  int ans = 0;
  for (int i = 0; i < n*3; i++) {
    int v = seg.query(0, ab[i].second + 1) + 1;
    // cout << i << " " << ab[i].first << " " << ab[i].second << " " << v << endl;
    seg.set_val(ab[i].second, v);
    ans = max(ans, v);
  }
  cout << ans << endl;
}

提出情報

ジャッジ結果