oj.uz

Submission #238412

# Submission time Handle Problem Language Result Execution time Memory
238412 2020-06-11T06:37:04 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
36 / 100
 500 ms 4100 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 256 KB Partially correct
2 Partially correct 5 ms 384 KB Partially correct
3 Partially correct 5 ms 384 KB Partially correct
4 Partially correct 9 ms 384 KB Partially correct
5 Partially correct 9 ms 384 KB Partially correct
6 Partially correct 13 ms 384 KB Partially correct
7 Partially correct 60 ms 632 KB Partially correct
8 Partially correct 16 ms 640 KB Partially correct
9 Partially correct 29 ms 884 KB Partially correct
10 Execution timed out 1090 ms 1732 KB Time limit exceeded
11 Partially correct 88 ms 1264 KB Partially correct
12 Partially correct 279 ms 2284 KB Partially correct
13 Partially correct 301 ms 2412 KB Partially correct
14 Partially correct 349 ms 3472 KB Partially correct
15 Partially correct 386 ms 3432 KB Partially correct
16 Partially correct 405 ms 3704 KB Partially correct
17 Partially correct 381 ms 3684 KB Partially correct
18 Execution timed out 1091 ms 3548 KB Time limit exceeded
19 Partially correct 341 ms 4024 KB Partially correct
20 Partially correct 407 ms 4100 KB Partially correct