Submission #238574

#	Time	Username	Problem	Language	Result	Execution time	Memory
238574		thecodingwizard	trapezoid (balkan11_trapezoid)	C++11	90 / 100	991 ms	5988 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ii pair<int, int>
#define f first
#define s second

const int mod = 30013;

int main() {
    int n; cin >> n;
    vector<ii> topLeft;
    vector<pair<ii, ii>> A;
    for (int i = 0; i < n; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        A.pb({{a,b},{c,d}});
        topLeft.pb({a,i});
    }
    sort(topLeft.begin(), topLeft.end());

    int tlIdx = 0;
    set<ii> q;
    map<int, ii> traps;
    ii dp[n];
    while (tlIdx != n) {
        while (!q.empty() && q.begin()->f < topLeft[tlIdx].f) {
            int x = q.begin()->s;
            q.erase(q.begin());
            auto it = traps.lower_bound(A[x].s.s);
            while (it != traps.end() && it->s.f <= dp[x].f) {
                if (it->s.f == dp[x].f) {
                    it->s.s = (it->s.s+dp[x].s)%mod;
                    it++;
                } else {
                    it = traps.erase(it);
                }
            }
            it = traps.lower_bound(A[x].s.s);
            int additional = 0;
            if (!traps.empty()) {
                if (it != traps.begin()) {
                    it--;
                    if (it->s.f > dp[x].f) continue;
                    if (it->s.f == dp[x].f) {
                        additional += it->s.s;
                    }
                }
            }
            traps[A[x].s.s] = make_pair(dp[x].f, (additional+dp[x].s)%mod);
        }

        int u = topLeft[tlIdx].s;
        int best = 1, ct = 1;
        if (!traps.empty()) {
            auto it = traps.lower_bound(A[u].s.f);
            if (it != traps.begin()) {
                it--;
                best = 1 + it->s.f;
                ct = it->s.s;
            }
        }
        dp[u] = make_pair(best, ct);
        q.insert({A[u].f.s, u});

        tlIdx++;
    }
    int ans = 0;
    int ans2 = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i].f > ans) {
            ans = dp[i].f; ans2 = dp[i].s;
        } else if (dp[i].f == ans) {
            ans2 = (ans2 + dp[i].s) % mod;
        }
    }

    cout << ans << " " << ans2 << endl;

    return 0;
}

• Subtask 1: 90 / 100