Submission #558823

#	Time	Username	Problem	Language	Result	Execution time	Memory
558823		yanndev	trapezoid (balkan11_trapezoid)	C++17	100 / 100	134 ms	17080 KiB

trapezoid

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;

const int MX = 400042;
const int MOD = 30013;

int n;
pair<int, ll> bit[MX];

struct Trap {
    int topL;
    int topR;
    int botL;
    int botR;
    bool operator<(const Trap& other) const {
        return topL < other.topL;
    }
} ls[100042];

int trapId[MX];
pair<int, ll> toSet[MX];

void add(int idx, pair<int, ll> val) {
    for (++idx; idx < MX; idx += (idx & -idx)) {
        if (bit[idx].fi == val.fi)
            bit[idx].se = (bit[idx].se + val.se) % MOD;
        else if (bit[idx].fi < val.fi)
            bit[idx].se = val.se % MOD;
        bit[idx].fi = max(bit[idx].fi, val.fi);
    }
}

pair<int, ll> query(int idx) {
    pair<int, int> ans {-1, 0};
    for (++idx; idx > 0; idx -= (idx & -idx)) {
        if (bit[idx].fi == ans.fi)
            ans.se = (ans.se + bit[idx].se) % MOD;
        else if (bit[idx].fi > ans.fi)
            ans.se = bit[idx].se;
        ans.fi = max(ans.fi, bit[idx].fi);
    }

    return ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    memset(trapId, -1, sizeof(trapId));
    vector<int> coords {};
    for (int i = 0; i < n; i++) {
        cin >> ls[i].topL >> ls[i].topR >> ls[i].botL >> ls[i].botR;
        coords.push_back(ls[i].topL);
        coords.push_back(ls[i].topR);
        coords.push_back(ls[i].botL);
        coords.push_back(ls[i].botR);
    }

    ls[n] = {0, 0, 0, 0};
    ls[n + 1] = {(int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1, (int)1e9 + 1};
    coords.push_back(0);
    coords.push_back(1e9 + 1);

    sort(coords.begin(), coords.end());
    coords.resize(unique(coords.begin(), coords.end()) - coords.begin());

    for (int i = 0; i <= n + 1; i++) {
        ls[i].topL = lower_bound(coords.begin(), coords.end(), ls[i].topL) - coords.begin();
        ls[i].topR = lower_bound(coords.begin(), coords.end(), ls[i].topR) - coords.begin();
        ls[i].botL = lower_bound(coords.begin(), coords.end(), ls[i].botL) - coords.begin();
        ls[i].botR = lower_bound(coords.begin(), coords.end(), ls[i].botR) - coords.begin();
        trapId[ls[i].topL] = i;
        trapId[ls[i].topR] = i;
    }

    add(0, {1, 1});

    for (int i = 1; i < (int)coords.size(); i++) {
        if (trapId[i] != -1) {
            int id = trapId[i];
            auto cur = ls[id];
            if (i == cur.topL) {
                auto dpVal = query(cur.botL);
                dpVal.first++;
                toSet[cur.topR] = dpVal;
            }

            if (i == cur.topR) {
                add(cur.botR, toSet[cur.topR]);
            }
        }
    }

    auto bst = query(MX - 2);
    cout << bst.fi - 2 << ' ' << (bst.se % MOD) << '\n';
}

• Subtask 1: 100 / 100