oj.uz

Submission #238402

# Submission time Handle Problem Language Result Execution time Memory
238402 2020-06-11T05:26:20 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
2 / 100
 261 ms 8676 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 5 ms 256 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 8 ms 512 KB Output isn't correct
6 Incorrect 11 ms 640 KB Output isn't correct
7 Incorrect 13 ms 640 KB Output isn't correct
8 Incorrect 16 ms 768 KB Output isn't correct
9 Incorrect 28 ms 1140 KB Output isn't correct
10 Incorrect 49 ms 1904 KB Output isn't correct
11 Incorrect 63 ms 2416 KB Output isn't correct
12 Incorrect 126 ms 4588 KB Output isn't correct
13 Incorrect 156 ms 5224 KB Output isn't correct
14 Incorrect 183 ms 6120 KB Output isn't correct
15 Incorrect 193 ms 6628 KB Output isn't correct
16 Incorrect 209 ms 6756 KB Output isn't correct
17 Incorrect 225 ms 7268 KB Output isn't correct
18 Incorrect 228 ms 7652 KB Output isn't correct
19 Incorrect 249 ms 8164 KB Output isn't correct
20 Incorrect 261 ms 8676 KB Output isn't correct