Submission #238405

#TimeUsernameProblemLanguageResultExecution timeMemory
238405thecodingwizardtrapezoid (balkan11_trapezoid)C++11
2 / 100
244 ms10324 KiB
#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> topRight, 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}});
        topRight.pb({b,i});
        topLeft.pb({a,i});
    }
    sort(topLeft.begin(), topLeft.end());
    sort(topRight.begin(), topRight.end());

    int tlIdx = 0, trIdx = 0;
    queue<int> q;
    map<int, int> traps;
    int dp[n];
    while (trIdx != n) {
        if (topLeft[tlIdx].f < topRight[trIdx].f) {
            while (!q.empty() && A[q.front()].f.s < topLeft[tlIdx].f) {
                if (!traps.empty()) {
                    auto it = traps.lower_bound(A[q.front()].s.s);
                    while (it != traps.end() && it->s <= dp[q.front()]) {
                        traps.erase(it->f);
                        if (traps.empty()) break;
                        it = traps.lower_bound(A[q.front()].s.s);
                    }
                }
                traps[A[q.front()].s.s] = dp[q.front()];
                q.pop();
            }
            tlIdx++;
        } else {
            int u = topRight[trIdx].s;
            int best = 1;
            if (!traps.empty()) {
                auto it = traps.lower_bound(A[u].s.f);
                if (it != traps.begin()) {
                    it--;
                    best += it->s;
                }
            }
            dp[u] = best;

            q.push(u);
            
            trIdx++;
        }
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dp[i]);
    }

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

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...