Submission #1222739

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222739		mariamtsagareli	trapezoid (balkan11_trapezoid)	C++20	12 / 100	149 ms	25200 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
using i = int;
const i MOD = 30013;

struct Seg {
    i mx;
    i cnt;
    Seg(i m=0, i c=0): mx(m), cnt(c) {}
};

Seg mergeSeg(const Seg &a, const Seg &b) {
    if (a.mx > b.mx) return a;
    if (b.mx > a.mx) return b;
    if (a.mx == 0) return Seg(0, 1);
    return Seg(a.mx, (a.cnt + b.cnt) % MOD);
}

struct ST {
    i n;
    vector<Seg> t;
    ST(i _n): n(_n), t(4*_n+4, Seg(0, 1)) {}

    Seg queryRec(i p, i l, i r, i ql, i qr) {
        if (r < ql || l > qr) return Seg(0, 1);
        if (ql <= l && r <= qr) return t[p];
        i m = (l + r) >> 1;
        return mergeSeg(
            queryRec(p<<1,    l,   m, ql, qr),
            queryRec(p<<1|1, m+1,   r, ql, qr)
        );
    }

    Seg query(i left, i right) {
        return left > right ? Seg(0, 1) : queryRec(1, 1, n, left, right);
    }

    void updateRec(i p, i l, i r, i pos, const Seg &val) {
        if (l == r) {
            t[p] = mergeSeg(t[p], val);
            return;
        }
        i m = (l + r) >> 1;
        if (pos <= m) updateRec(p<<1,    l,   m, pos, val);
        else         updateRec(p<<1|1, m+1,   r, pos, val);
        t[p] = mergeSeg(t[p<<1], t[p<<1|1]);
    }

    void update(i pos, const Seg &val) {
        updateRec(1, 1, n, pos, val);
    }
};

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

    i N;
    cin >> N;
    struct Trap { i a, b, c, d; };
    vector<Trap> A(N);
    vector<i> coords;
    coords.reserve(4 * N);

    for (i idx = 0; idx < N; idx++) {
        cin >> A[idx].a >> A[idx].b >> A[idx].c >> A[idx].d;
        coords.push_back(A[idx].a);
        coords.push_back(A[idx].b);
        coords.push_back(A[idx].c);
        coords.push_back(A[idx].d);
    }

    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    auto getId = [&](i v) {
        return (i)(lower_bound(coords.begin(), coords.end(), v) - coords.begin() + 1);
    };

    i M = coords.size();
    for (auto &t : A) {
        t.a = getId(t.a);
        t.b = getId(t.b);
        t.c = getId(t.c);
        t.d = getId(t.d);
    }

    sort(A.begin(), A.end(), [](const Trap &u, const Trap &v) {
        return u.a != v.a ? u.a < v.a : u.b < v.b;
    });

    ST stTop(M), stBot(M);
    vector<Seg> dp(N);

    for (i idx = 0; idx < N; idx++) {
        Seg leftBest = stTop.query(1, A[idx].a - 1);
        Seg downBest = stBot.query(1, A[idx].c - 1);
        Seg best = mergeSeg(leftBest, downBest);
        dp[idx] = Seg(best.mx + 1, best.cnt);
        stTop.update(A[idx].b, dp[idx]);
        stBot.update(A[idx].d, dp[idx]);
    }

    i maxLen = 0;
    for (auto &s : dp) maxLen = max(maxLen, s.mx);

    i ways = 0;
    for (auto &s : dp) if (s.mx == maxLen) ways = (ways + s.cnt) % MOD;

    cout << maxLen << " " << ways;
    return 0;
}

• Subtask 1: 12 / 100