oj.uz

Submission #529524

# Submission time Handle Problem Language Result Execution time Memory
529524 2022-02-23T06:00:50 Z zxcvbnm trapezoid (balkan11_trapezoid) C++14
4 / 100
 50 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[1] && 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
4.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 2 ms 332 KB Output isn't correct
6 Incorrect 2 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 480 KB Output isn't correct
10 Incorrect 12 ms 716 KB Output isn't correct
11 Partially correct 10 ms 844 KB Partially correct
12 Incorrect 22 ms 1472 KB Output isn't correct
13 Incorrect 26 ms 1648 KB Output isn't correct
14 Incorrect 32 ms 1928 KB Output isn't correct
15 Incorrect 31 ms 2068 KB Output isn't correct
16 Incorrect 33 ms 2084 KB Output isn't correct
17 Incorrect 35 ms 2312 KB Output isn't correct
18 Incorrect 37 ms 2420 KB Output isn't correct
19 Incorrect 50 ms 2432 KB Output isn't correct
20 Incorrect 48 ms 2648 KB Output isn't correct