oj.uz

Submission #529536

# Submission time Handle Problem Language Result Execution time Memory
529536 2022-02-23T06:10:38 Z zxcvbnm trapezoid (balkan11_trapezoid) C++14
2 / 100
 51 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 l < r;
    };

    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 1 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 2 ms 332 KB Output isn't correct
8 Incorrect 2 ms 392 KB Output isn't correct
9 Incorrect 7 ms 460 KB Output isn't correct
10 Incorrect 9 ms 764 KB Output isn't correct
11 Incorrect 16 ms 844 KB Output isn't correct
12 Incorrect 24 ms 1496 KB Output isn't correct
13 Incorrect 31 ms 1636 KB Output isn't correct
14 Incorrect 33 ms 1928 KB Output isn't correct
15 Incorrect 36 ms 2008 KB Output isn't correct
16 Incorrect 39 ms 2068 KB Output isn't correct
17 Incorrect 51 ms 2276 KB Output isn't correct
18 Incorrect 40 ms 2392 KB Output isn't correct
19 Incorrect 44 ms 2448 KB Output isn't correct
20 Incorrect 47 ms 2648 KB Output isn't correct