oj.uz

Submission #238398

# Submission time Handle Problem Language Result Execution time Memory
238398 2020-06-11T05:16:21 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
2 / 100
 234 ms 10316 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> 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) {
                auto it = traps.lower_bound(A[q.front()].s.s);
                while (it != traps.end() && it->s <= dp[q.front()]) {
                    it = traps.erase(it);
                }
                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;
}

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 384 KB Partially correct
2 Incorrect 5 ms 256 KB Output isn't correct
3 Incorrect 5 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 12 ms 640 KB Output isn't correct
8 Runtime error 15 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 25 ms 768 KB Output isn't correct
10 Incorrect 49 ms 1904 KB Output isn't correct
11 Runtime error 60 ms 2924 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 118 ms 2656 KB Output isn't correct
13 Incorrect 138 ms 2796 KB Output isn't correct
14 Runtime error 172 ms 8292 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 180 ms 8552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 187 ms 8932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 203 ms 9316 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Incorrect 218 ms 7756 KB Output isn't correct
19 Runtime error 219 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 234 ms 10316 KB Execution killed with signal 11 (could be triggered by violating memory limits)