Submission #1222750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222750		mariamtsagareli	trapezoid (balkan11_trapezoid)	C++20	100 / 100	94 ms	7236 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
using i = int;
const i MOD = 30013;
struct Trap { i a, b, c, d; };
struct Seg { i mx, cnt; Seg(i m=0, i c=0): mx(m), cnt(c) {} };
Seg mergeSeg(const Seg &x, const Seg &y) {
    if (x.mx > y.mx) return x;
    if (y.mx > x.mx) return y;
    if (x.mx == 0) return Seg(0, 1);
    return Seg(x.mx, (x.cnt + y.cnt) % MOD);
}

struct BITSeg {
    i n;
    vector<Seg> t;
    BITSeg(i m): n(m), t(m+1, Seg(0,1)) {}
    void update(i pos, const Seg &v) {
        for (; pos <= n; pos += pos & -pos)
            t[pos] = mergeSeg(t[pos], v);
    }
    Seg query(i pos) {
        Seg res(0,1);
        for (; pos > 0; pos -= pos & -pos)
            res = mergeSeg(res, t[pos]);
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    i N;
    if (!(cin >> N)) return 0;
    vector<Trap> A(N);
    vector<i> C;
    C.reserve(4 * N);
    for (i idx = 0; idx < N; idx++) {
        cin >> A[idx].a >> A[idx].b >> A[idx].c >> A[idx].d;
        C.push_back(A[idx].a);
        C.push_back(A[idx].b);
        C.push_back(A[idx].c);
        C.push_back(A[idx].d);
    }
    sort(C.begin(), C.end());
    C.erase(unique(C.begin(), C.end()), C.end());
    auto id = [&](i v) {
        return (i)(lower_bound(C.begin(), C.end(), v) - C.begin() + 1);
    };
    for (i idx = 0; idx < N; idx++) {
        A[idx].a = id(A[idx].a);
        A[idx].b = id(A[idx].b);
        A[idx].c = id(A[idx].c);
        A[idx].d = id(A[idx].d);
    }
    sort(A.begin(), A.end(), [](const Trap &x, const Trap &y) {
        return x.a < y.a;
    });
    i M = C.size();
    vector<i> orderB(N);
    for (i idx = 0; idx < N; idx++) orderB[idx] = idx;
    sort(orderB.begin(), orderB.end(), [&](i x, i y) {
        return A[x].b < A[y].b;
    });
    BITSeg bit(M);
    vector<Seg> dp(N);
    i ptrB = 0;
    for (i idx = 0; idx < N; idx++) {
        while (ptrB < N && A[orderB[ptrB]].b < A[idx].a) {
            i j = orderB[ptrB++];
            bit.update(A[j].d, dp[j]);
        }
        Seg best = bit.query(A[idx].c - 1);
        dp[idx] = Seg(best.mx + 1, best.cnt);
    }
    i K = 0;
    for (i idx = 0; idx < N; idx++)
        K = max(K, dp[idx].mx);
    i total = 0;
    for (i idx = 0; idx < N; idx++)
        if (dp[idx].mx == K)
            total = (total + dp[idx].cnt) % MOD;
    cout << K << " " << total;
    return 0;
}

• Subtask 1: 100 / 100