제출 #1346150

#제출 시각아이디문제언어결과실행 시간메모리
1346150JahonaliX사다리꼴 (balkan11_trapezoid)C++20
100 / 100
130 ms33376 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int mod = 30013, inf = 1e17;

struct node { int mx, cnt; };

node merge(node left, node right) {
    if (left.mx > right.mx) return left;
    if (right.mx > left.mx) return right;
    return {left.mx, (left.cnt + right.cnt) % mod};
}

struct segment_tree {
    int n;
    vector<node> t;
    segment_tree(int n) : n(n), t(n << 2) {}
    void update(int i, int dp, int cn, int v = 1, int l = 0, int r = -1) {
        if (r < 0) r += n;
        if (l == r) t[v] = {dp, cn};
        else {
            int m = (l + r) >> 1;
            if (i <= m) update(i, dp, cn, v << 1, l, m);
            else update(i, dp, cn, v << 1 | 1, m + 1, r);
            t[v] = merge(t[v << 1], t[v << 1 | 1]);
        }
    }
    node get(int L, int R, int v = 1, int l = 0, int r = -1) {
        if (r < 0) r += n;
        if (L <= l && r <= R) return t[v];
        int m = (l + r) >> 1;
        if (R <= m) return get(L, R, v << 1, l, m);
        if (L > m) return get(L, R, v << 1 | 1, m + 1, r);
        return merge(get(L, R, v << 1, l, m), get(L, R, v << 1 | 1, m + 1, r));
    }
};

int32_t main() {
#ifdef JahonaliX
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, ans = 0, cn = 1;
    cin >> n;
    vector<int> a(n), b(n), c(n), d(n), dp(n, 1), cnt(n, 1), o(n), u;
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&] (int i, int j) { return a[i] < a[j]; });
    auto aa = a, bb = b, cc = c, dd = d;
    for (int i = 0; i < n; ++i) a[i] = aa[o[i]], b[i] = bb[o[i]], c[i] = cc[o[i]], d[i] = dd[o[i]];
    for (int i : a) u.emplace_back(i);
    for (int i : b) u.emplace_back(i);
    for (int i : c) u.emplace_back(i);
    for (int i : d) u.emplace_back(i);
    sort(u.begin(), u.end()), u.erase(unique(u.begin(), u.end()), u.end());
    for (int &i : a) i = lower_bound(u.begin(), u.end(), i) - u.begin();
    for (int &i : b) i = lower_bound(u.begin(), u.end(), i) - u.begin();
    for (int &i : c) i = lower_bound(u.begin(), u.end(), i) - u.begin();
    for (int &i : d) i = lower_bound(u.begin(), u.end(), i) - u.begin();
    set<pair<int, int>> st;
    segment_tree s(u.size());
    for (int i = 0; i < n; ++i) {
        while (st.size() && st.begin()->first < a[i]) {
            auto [tr, j] = *st.begin();
            st.erase(st.begin()), s.update(d[j], dp[j] + 1, cnt[j]);
        }
        auto p = s.get(0, c[i]);
        if (p.mx == 0) {
            st.emplace(b[i], i);
            continue;
        }
        dp[i] = p.mx, cnt[i] = p.cnt;
        st.emplace(b[i], i);
    }
    for (int i = 0; i < n; ++i) {
        if (dp[i] > ans) ans = dp[i], cn = cnt[i];
        else if (dp[i] == ans) cn += cnt[i], cn %= mod;
    }
    cout << ans << ' ' << cn;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...