Submission #238412

#	Time	Username	Problem	Language	Result	Execution time	Memory
238412		thecodingwizard	trapezoid (balkan11_trapezoid)	C++11	36 / 100	1091 ms	4100 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

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

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, int> traps;
    int dp[n];
    while (tlIdx != n) {
        while (!q.empty() && q.begin()->f < topLeft[tlIdx].f) {
            int x = q.begin()->s;
            auto it = traps.lower_bound(A[x].s.s);
            while (it != traps.end() && it->s <= dp[x]) {
                it = traps.erase(it);
            }
            traps[A[x].s.s] = dp[x];
            q.erase(q.begin());
        }

        int u = topLeft[tlIdx].s;
        int best = 1;
        if (!traps.empty()) {
            /*
            auto it = traps.lower_bound(A[u].s.f);
            if (it != traps.begin()) {
                it--;
                best += it->s;
            }
            */
            for (auto v : traps) {
                if (v.f < A[u].s.f) best = max(best, 1 + v.s);
            }
        }
        dp[u] = best;
        q.insert({A[u].f.s, u});

        tlIdx++;
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }

    cout << ans <<  " 0" << endl;

    return 0;
}

• Subtask 1: 36 / 100