oj.uz

Submission #238400

# Submission time Handle Problem Language Result Execution time Memory
238400 2020-06-11T05:24:37 Z thecodingwizard trapezoid (balkan11_trapezoid) C++11
2 / 100
 271 ms 8484 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.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 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 8 ms 512 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 Incorrect 14 ms 768 KB Output isn't correct
9 Incorrect 26 ms 1148 KB Output isn't correct
10 Incorrect 53 ms 1904 KB Output isn't correct
11 Incorrect 61 ms 2416 KB Output isn't correct
12 Incorrect 134 ms 4584 KB Output isn't correct
13 Incorrect 147 ms 5352 KB Output isn't correct
14 Incorrect 189 ms 6116 KB Output isn't correct
15 Incorrect 205 ms 6504 KB Output isn't correct
16 Incorrect 204 ms 6756 KB Output isn't correct
17 Incorrect 220 ms 7268 KB Output isn't correct
18 Incorrect 216 ms 7804 KB Output isn't correct
19 Incorrect 226 ms 8164 KB Output isn't correct
20 Incorrect 271 ms 8484 KB Output isn't correct