Submission #1222748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222748		mariamtsagareli	trapezoid (balkan11_trapezoid)	C++20	30 / 100	157 ms	27248 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 ST {
    i n; vector<Seg> t;
    ST(i m): n(m), t(4*m+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 l, i r) { return l > r ? Seg(0,1) : queryRec(1,1,n,l,r); }
    void updateRec(i p, i l, i r, i pos, const Seg &v) {
        if (l == r) { t[p] = mergeSeg(t[p], v); return; }
        i m = (l + r) >> 1;
        if (pos <= m) updateRec(p<<1,    l,   m, pos, v);
        else         updateRec(p<<1|1, m+1,   r, pos, v);
        t[p] = mergeSeg(t[p<<1], t[p<<1|1]);
    }
    void update(i pos, const Seg &v) { updateRec(1,1,n,pos,v); }
};

struct BIT {
    i n; vector<i> f;
    BIT(i m): n(m), f(m+1,0) {}
    void add(i pos, i v) {
        for (; pos <= n; pos += pos & -pos)
            f[pos] = (f[pos] + v) % MOD;
    }
    i sum(i pos) {
        i s = 0;
        for (; pos > 0; pos -= pos & -pos)
            s = (s + f[pos]) % MOD;
        return s;
    }
};

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

    i N; cin >> N;
    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); };
    i M = C.size();
    for (auto &t : A) {
        t.a = id(t.a);
        t.b = id(t.b);
        t.c = id(t.c);
        t.d = id(t.d);
    }
    sort(A.begin(), A.end(), [](const Trap &x, const Trap &y){
        return x.a != y.a ? x.a < y.a : x.b < y.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 cur = mergeSeg(leftBest, downBest);
        dp[idx] = Seg(cur.mx + 1, cur.cnt);
        stTop.update(A[idx].b, dp[idx]);
        stBot.update(A[idx].d, dp[idx]);
    }
    i K = 0;
    for (auto &s : dp) K = max(K, s.mx);
    vector<vector<i>> by(K+1);
    for (i idx = 0; idx < N; idx++) by[dp[idx].mx].push_back(idx);

    vector<i> cnt2(N);
    for (i k = 1; k < K; k++) {
        BIT bit(M);
        for (i idx : by[k]) bit.add(A[idx].d, dp[idx].cnt);
        for (i idx : by[k+1]) cnt2[idx] = bit.sum(A[idx].c - 1);
        for (i idx : by[k+1]) dp[idx].cnt = cnt2[idx];
    }
    i total = 0;
    for (i idx : by[K]) total = (total + dp[idx].cnt) % MOD;
    cout << K << " " << total;
    return 0;
}

• Subtask 1: 30 / 100