제출 #1286299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286299		LIA	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	77 ms	12788 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define loop(i, s, e) for (ll i = s; i < e; ++i)
#define pll pair<ll, ll>
const ll MOD = 30013;

struct Fen {
  vector<pll> b;
  ll n;
  Fen(ll N) {
    n = N;
    b.assign(n + 2, {0, 0});
  }
  pll merge(pll a, pll c) {
    if (a.first < c.first)
      return c;
    if (a.first > c.first)
      return a;
    if (a.first == 0)
      return {0, (a.second + c.second) % MOD};
    return {a.first, (a.second + c.second) % MOD};
  }
  void update(ll i, pll v) {
    for (++i; i <= n; i += i & -i) {
      if (b[i].first < v.first)
        b[i] = v;
      else if (b[i].first == v.first) {
        b[i].second = (b[i].second + v.second) % MOD;
      }
    }
  }
  pll query(ll r) {
    pll ans = {0, 0};
    for (++r; r > 0; r -= r & -r)
      ans = merge(ans, b[r]);
    return ans;
  }
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  if (!(cin >> n))
    return 0;
  vll a(n), b(n), c(n), d(n);
  loop(i, 0, n) cin >> a[i] >> b[i] >> c[i] >> d[i];
  vector<ll> vals;
  vals.reserve(2 * n);
  loop(i, 0, n) {
    vals.push_back(c[i]);
    vals.push_back(d[i]);
  }
  sort(vals.begin(), vals.end());
  vals.erase(unique(vals.begin(), vals.end()), vals.end());
  auto id = [&](ll x) { return (ll)(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); };

  vector<tuple<ll, int, int>> ev;
  ev.reserve(2 * n);
  loop(i, 0, n) {
    ev.emplace_back(a[i], 0, i);
    ev.emplace_back(b[i], 1, i);
  }
  sort(ev.begin(), ev.end(), [&](auto& x, auto& y) {
    if (get<0>(x) != get<0>(y))
      return get<0>(x) < get<0>(y);
    return get<1>(x) > get<1>(y);
  });

  Fen ft((ll)vals.size());
  vll dp(n), ways(n);
  ll best = 0, cnt = 0;

  for (auto& e : ev) {
    ll x;
    int t, i;
    tie(x, t, i) = e;
    if (t == 0) {
      ll k = (ll)(lower_bound(vals.begin(), vals.end(), c[i]) - vals.begin()) - 1;
      pll q = {0, 0};
      if (k >= 0)
        q = ft.query(k);
      ll len = q.first + 1;
      ll num = q.second % MOD;
      if (q.first == 0)
        num = 1;
      dp[i] = len;
      ways[i] = num % MOD;
    } else {
      ll pos = id(d[i]);
      ft.update(pos, {dp[i], ways[i]});
    }
  }

  loop(i, 0, n) {
    if (dp[i] > best) {
      best = dp[i];
      cnt = ways[i];
    } else if (dp[i] == best) {
      cnt = (cnt + ways[i]) % MOD;
    }
  }
  cout << best << " " << (cnt % MOD) << "\n";
  return 0;
}

• Subtask 1: 100 / 100