Submission #238408

#	Time	Username	Problem	Language	Result	Execution time	Memory
238408		thecodingwizard	trapezoid (balkan11_trapezoid)	C++11	0 / 100	216 ms	9572 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

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

vector<ii> topRight, topLeft;
vector<pair<ii, ii>> A;
queue<int> q;
map<int, int> traps;

int main() {
    int n; cin >> n;
    int dp[n];
    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;
    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;
}

Compilation message (stderr)

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:17:9: warning: unused variable 'dp' [-Wunused-variable]
     int dp[n];
         ^~

• Subtask 1: 0 / 100