oj.uz

Submission #238411

# Submission time Handle Problem Language Result Execution time Memory
238411 2020-06-11T06:31:50 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
4 / 100
 239 ms 7140 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;
            }
        }
        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
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 256 KB Partially correct
2 Incorrect 5 ms 384 KB Output isn't correct
3 Incorrect 6 ms 384 KB Output isn't correct
4 Incorrect 6 ms 384 KB Output isn't correct
5 Incorrect 9 ms 384 KB Output isn't correct
6 Incorrect 11 ms 512 KB Output isn't correct
7 Incorrect 13 ms 640 KB Output isn't correct
8 Incorrect 14 ms 640 KB Output isn't correct
9 Incorrect 26 ms 768 KB Output isn't correct
10 Incorrect 50 ms 1776 KB Output isn't correct
11 Incorrect 61 ms 1264 KB Output isn't correct
12 Incorrect 120 ms 2284 KB Output isn't correct
13 Incorrect 144 ms 2596 KB Output isn't correct
14 Incorrect 180 ms 3432 KB Output isn't correct
15 Incorrect 185 ms 3436 KB Output isn't correct
16 Incorrect 208 ms 3560 KB Output isn't correct
17 Incorrect 206 ms 3684 KB Output isn't correct
18 Incorrect 221 ms 7140 KB Output isn't correct
19 Incorrect 224 ms 3916 KB Output isn't correct
20 Partially correct 239 ms 4208 KB Partially correct