Submission #558823

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
558823	2022-05-08T13:55:06 Z	yanndev	trapezoid (balkan11_trapezoid)	C++17	100 / 100	134 ms	17080 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1876 KB	Output is correct
2	Correct	2 ms	1876 KB	Output is correct
3	Correct	2 ms	1996 KB	Output is correct
4	Correct	2 ms	2004 KB	Output is correct
5	Correct	3 ms	2260 KB	Output is correct
6	Correct	5 ms	2388 KB	Output is correct
7	Correct	5 ms	2440 KB	Output is correct
8	Correct	7 ms	2644 KB	Output is correct
9	Correct	13 ms	3436 KB	Output is correct
10	Correct	30 ms	4428 KB	Output is correct
11	Correct	37 ms	6032 KB	Output is correct
12	Correct	59 ms	9824 KB	Output is correct
13	Correct	70 ms	11260 KB	Output is correct
14	Correct	84 ms	13504 KB	Output is correct
15	Correct	96 ms	13048 KB	Output is correct
16	Correct	103 ms	14276 KB	Output is correct
17	Correct	134 ms	16436 KB	Output is correct
18	Correct	95 ms	12636 KB	Output is correct
19	Correct	109 ms	14744 KB	Output is correct
20	Correct	129 ms	17080 KB	Output is correct