oj.uz

Submission #856478

# Submission time Handle Problem Language Result Execution time Memory
856478 2023-10-03T16:19:36 Z ArminAzimi trapezoid (balkan11_trapezoid) C++14
40 / 100
 128 ms 11964 KB 
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<pair <int, int>, null_type,less<pair <int, int>>, rb_tree_tag,tree_order_statistics_node_update> 

const int MAXN = 2e5 + 10, MAXM = 1e2 + 10, MOD = 998244353, MOD1 = 1e9 + 9, SQ = 350;
const long long INF = 1e9 + 11;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int a[MAXN], b[MAXN], c[MAXN], d[MAXN];
int id_a[MAXN], id_b[MAXN];
int seg[4 * MAXN];
int dp[MAXN];

void upd(int l, int r, int id, int ind, int val) {
    if (l == r) {
        seg[id] = val;
        return;
    }

    int mid = (l + r) / 2;
    if (ind <= mid)
        upd(l, mid, 2 * id, ind, val);
    else
        upd(mid + 1, r, 2 * id + 1, ind, val);

    seg[id] = max(seg[2 * id], seg[2 * id + 1]);
}

int get(int l, int r, int id, int l1, int r1) {
    if (r < l1 || r1 < l)
        return 0;
    if (l1 <= l && r <= r1)
        return seg[id];
    
    int mid = (l + r) / 2;
    return max(get(l, mid, 2 * id, l1, r1), get(mid + 1, r, 2 * id + 1, l1, r1));
}


void solve() {
    int n;
    cin >> n;

    vector <int> kol1, kol2;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        kol1.push_back(a[i]);
        kol1.push_back(b[i]);
        kol2.push_back(c[i]);
        kol2.push_back(d[i]);
    }

    sort(kol1.begin(), kol1.end());
    kol1.resize(unique(kol1.begin(), kol1.end()) - kol1.begin());

    sort(kol2.begin(), kol2.end());
    kol2.resize(unique(kol2.begin(), kol2.end()) - kol2.begin());

    for (int i = 1; i <= n; i++) {
        a[i] = lower_bound(kol1.begin(), kol1.end(), a[i]) - kol1.begin();
        b[i] = lower_bound(kol1.begin(), kol1.end(), b[i]) - kol1.begin();
        c[i] = lower_bound(kol2.begin(), kol2.end(), c[i]) - kol2.begin();
        d[i] = lower_bound(kol2.begin(), kol2.end(), d[i]) - kol2.begin();

        id_a[a[i]] = i;
        id_b[b[i]] = i;
    }

    for (int i = 0; i < 2 * n; i++) {
        if (id_a[i]) {
            int ind = id_a[i];
            int l1 = c[ind];

            dp[i] = get(0, 2 * n, 1, 0, l1) + 1;    
        }
        else {
            int ind = id_b[i];
            int index = d[ind];

            upd(0, 2 * n, 1, index, dp[a[ind]]);
        }
    }
    
    int ans = 0;
    for (int i = 0; i < 2 * n; i++)
        ans = max(ans, dp[i]);

    cout << ans << " 0" << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    // cin >> q;
    
    while (q--) {
        solve();
    }
}

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 6488 KB Partially correct
2 Partially correct 1 ms 6488 KB Partially correct
3 Partially correct 1 ms 6488 KB Partially correct
4 Partially correct 2 ms 6492 KB Partially correct
5 Partially correct 2 ms 6748 KB Partially correct
6 Partially correct 3 ms 6872 KB Partially correct
7 Partially correct 5 ms 6748 KB Partially correct
8 Partially correct 6 ms 7004 KB Partially correct
9 Partially correct 10 ms 7260 KB Partially correct
10 Partially correct 20 ms 8324 KB Partially correct
11 Partially correct 27 ms 8260 KB Partially correct
12 Partially correct 52 ms 9928 KB Partially correct
13 Partially correct 64 ms 10180 KB Partially correct
14 Partially correct 73 ms 11192 KB Partially correct
15 Partially correct 83 ms 11092 KB Partially correct
16 Partially correct 92 ms 11196 KB Partially correct
17 Partially correct 96 ms 11708 KB Partially correct
18 Partially correct 87 ms 11712 KB Partially correct
19 Partially correct 103 ms 11904 KB Partially correct
20 Partially correct 128 ms 11964 KB Partially correct