oj.uz

Submission #529530

# Submission time Handle Problem Language Result Execution time Memory
529530 2022-02-23T06:04:08 Z zxcvbnm trapezoid (balkan11_trapezoid) C++14
2 / 100
 40 ms 2648 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<array<int, 4>> a(n);
    for(auto& i : a) {
        for(auto& j : i) {
            cin >> j;
        }
    }

    auto cmp = [](const auto& l, const auto& r) {
        return r[0] > l[2] && r[2] > l[3];
    };

    auto ok = [&](int i, int j) {
        return a[j][0] > a[i][1] && a[j][2] > a[i][3];
    };

    sort(a.begin(), a.end(), cmp);
//    for(auto& i : a) {
//        for(auto& j : i) {
//            cout << j << " ";
//        }
//        cout << "\n";
//    }

//    bool can[n][n];
//    memset(can, false, sizeof can);
//
//    for(int i = 0; i < n; i++) {
//        for(int j = i+1; j < n; j++) {
//            can[i][j] = can[j][i] = ok(i, j);
//        }
//    }

    vector<int> dp(n, 1);
    vector<int> mx(n, 1);
    for(int i = 0; i < n; i++) {
        int l = 0, r = i-1, ans = -1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (ok(mid, i)) {
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }

        if (ans == -1) continue;
        dp[i] = dp[i] + mx[ans];
        mx[i] = max(mx[i-1], dp[i]);
    }

    cout << mx[n-1] << " " << mx[n-1] << "\n";
    return 0;
}

Subtask #1
2.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 204 KB Partially correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 0 ms 204 KB Output isn't correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Incorrect 3 ms 332 KB Output isn't correct
8 Incorrect 2 ms 332 KB Output isn't correct
9 Incorrect 4 ms 460 KB Output isn't correct
10 Incorrect 9 ms 776 KB Output isn't correct
11 Incorrect 10 ms 840 KB Output isn't correct
12 Incorrect 21 ms 1484 KB Output isn't correct
13 Incorrect 24 ms 1612 KB Output isn't correct
14 Incorrect 30 ms 1932 KB Output isn't correct
15 Incorrect 31 ms 2004 KB Output isn't correct
16 Incorrect 33 ms 2068 KB Output isn't correct
17 Incorrect 34 ms 2296 KB Output isn't correct
18 Incorrect 38 ms 2368 KB Output isn't correct
19 Incorrect 37 ms 2444 KB Output isn't correct
20 Incorrect 40 ms 2648 KB Output isn't correct