oj.uz

Submission #238405

# Submission time Handle Problem Language Result Execution time Memory
238405 2020-06-11T05:31:20 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
2 / 100
 244 ms 10324 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) {
                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;
}

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 4 ms 256 KB Partially correct
2 Incorrect 5 ms 256 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 14 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 35 ms 760 KB Output isn't correct
10 Incorrect 50 ms 1904 KB Output isn't correct
11 Runtime error 63 ms 2928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 121 ms 2540 KB Output isn't correct
13 Incorrect 142 ms 2796 KB Output isn't correct
14 Runtime error 179 ms 8324 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 188 ms 8708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 200 ms 8932 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 208 ms 9188 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Incorrect 223 ms 7780 KB Output isn't correct
19 Runtime error 223 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 244 ms 10324 KB Execution killed with signal 11 (could be triggered by violating memory limits)