Submission #1221030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221030		takoshanava	trapezoid (balkan11_trapezoid)	C++20	30 / 100	135 ms	21124 KiB

trapezoid

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;

const int MOD = 30013;
const int N = 200005;

int a[N], b[N], c[N], d[N];
int dp[N], cnt[N];

int mx[4 * N];
int scnt[4 * N];

vector<int> cmp;

int compress(vector<int>& vals) {
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    return vals.size();
}

int get(int x) {
    return lower_bound(cmp.begin(), cmp.end(), x) - cmp.begin() + 1;
}

void update(int v, int tl, int tr, int pos, int dp1, int cnt1) {
    if (tl == tr) {
        if (mx[v] < dp1) {
            mx[v] = dp1;
            scnt[v] = cnt1;
        } else if (mx[v] == dp1) {
            scnt[v] = (scnt[v] + cnt1) % MOD;
        }
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos <= tm)
        update(2*v, tl, tm, pos, dp1, cnt1);
    else
        update(2*v+1, tm+1, tr, pos, dp1, cnt1);

    if (mx[2*v] > mx[2*v+1]) {
        mx[v] = mx[2*v];
        scnt[v] = scnt[2*v];
    } else if (mx[2*v+1] > mx[2*v]) {
        mx[v] = mx[2*v+1];
        scnt[v] = scnt[2*v+1];
    } else {
        mx[v] = mx[2*v];
        scnt[v] = (scnt[2*v] + scnt[2*v+1]) % MOD;
    }
}

pair<int,int> query(int v, int tl, int tr, int l, int r) {
    if (l > r) return {0, 0};
    if (l <= tl and tr <= r) return {mx[v], scnt[v]};
    int tm = (tl + tr) / 2;
    pair<int,int> left = query(2*v, tl, tm, l, min(r, tm));
    pair<int,int> right = query(2*v+1, tm+1, tr, max(l, tm+1), r);
    if (left.first > right.first) return left;
    if (right.first > left.first) return right;
    return {left.first, (left.second + right.second) % MOD};
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        cmp.pb(a[i]);
        cmp.pb(b[i]);
        cmp.pb(c[i]);
        cmp.pb(d[i]);
    }

    int M = compress(cmp);
    for (int i = 0; i < n; i++) {
        a[i] = get(a[i]);
        b[i] = get(b[i]);
        c[i] = get(c[i]);
        d[i] = get(d[i]);
    }

    vector<int> order(n);
    iota(order.begin(), order.end(), 0);

    sort(order.begin(), order.end(), [&](int i, int j) {
        if (b[i] != b[j]) return b[i] < b[j];
        return d[i] < d[j];
    });

    int ans = 0, ways = 0;
    for (int idx = 0; idx < n; idx++) {
        int i = order[idx];
        pair<int,int> res = query(1, 1, M, 1, c[i] - 1);

        dp[i] = res.first + 1;
        cnt[i] = (res.first == 0 ? 1 : res.second);

        update(1, 1, M, d[i], dp[i], cnt[i]);

        if (dp[i] > ans) {
            ans = dp[i];
            ways = cnt[i];
        } else if (dp[i] == ans) {
            ways = (ways + cnt[i]) % MOD;
        }
    }

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

• Subtask 1: 30 / 100