oj.uz

Submission #238401

# Submission time Handle Problem Language Result Execution time Memory
238401 2020-06-11T05:25:32 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
2 / 100
 251 ms 9956 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);
                    break;
                }
                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.end()) {
                    it--;
                    best += it->s;
                } else if (it->f < A[u].s.f) {
                    best += it->s;
                } else 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 384 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 8 ms 384 KB Output isn't correct
6 Incorrect 10 ms 512 KB Output isn't correct
7 Incorrect 12 ms 640 KB Output isn't correct
8 Incorrect 14 ms 640 KB Output isn't correct
9 Incorrect 25 ms 892 KB Output isn't correct
10 Incorrect 49 ms 1904 KB Output isn't correct
11 Runtime error 62 ms 2928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 125 ms 3176 KB Output isn't correct
13 Incorrect 146 ms 3688 KB Output isn't correct
14 Runtime error 181 ms 8168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Incorrect 187 ms 4328 KB Output isn't correct
16 Incorrect 200 ms 4712 KB Output isn't correct
17 Incorrect 214 ms 4968 KB Output isn't correct
18 Incorrect 219 ms 7652 KB Output isn't correct
19 Runtime error 224 ms 9956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Incorrect 251 ms 5348 KB Output isn't correct