제출 #1216440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1216440		nh0902	trapezoid (balkan11_trapezoid)	C++20	90 / 100	136 ms	70864 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10;

const int mod = 30013;

struct Tr {
    int a, b, c, d;
};

int n;

Tr tr[N];

int dp[N], dp_cnt[N];

int child[21 * N][2], st_max[21 * N], st_cnt[21 * N];

int cur, ver[N];

int build(int l, int r) {
    if (l == r) {
        cur ++;
        return cur;
    }

    cur ++;
    int id = cur;
    int mid = (l + r) / 2;

    child[id][0] = build(l, mid);
    child[id][1] = build(mid + 1, r);

    return id;
}

int update(int id, int l, int r, int p, int val, int cnt) {
    if (l == r) {
        cur ++;
        st_max[cur] = val;
        st_cnt[cur] = cnt;
        return cur;
    }

    cur ++;
    int new_id = cur;
    int mid = (l + r) / 2;

    if (p <= mid) {
        child[new_id][0] = update(child[id][0], l, mid, p, val, cnt);
        child[new_id][1] = child[id][1];
    }
    else {
        child[new_id][0] = child[id][0];
        child[new_id][1] = update(child[id][1], mid + 1, r, p, val, cnt);
    }

    if (st_max[child[new_id][0]] >= st_max[child[new_id][1]]) {
        st_max[new_id] = st_max[child[new_id][0]];
        st_cnt[new_id] = st_cnt[child[new_id][0]];
    }

    if (st_max[child[new_id][0]] <= st_max[child[new_id][1]]) {
        st_max[new_id] = st_max[child[new_id][1]];
        st_cnt[new_id] += st_cnt[child[new_id][1]];
        st_cnt[new_id] %= mod;
    }

    return new_id;
}

pair<int, int> get(int id, int l, int r, int u, int v) {
    if (r < u || v < l) return {0, 0};

    if (u <= l && r <= v) return {st_max[id], st_cnt[id]};

    int mid = (l + r) / 2;
    pair<int, int> ans1 = get(child[id][0], l, mid, u, v);
    pair<int, int> ans2 = get(child[id][1], mid + 1, r, u, v);

    if (ans1.first > ans2.first) return ans1;
    else if (ans1.first < ans2.first) return ans2;
    return {ans1.first, (ans1.second + ans2.second) % mod};
}

bool cmp(Tr t1, Tr t2) {
    return t1.b < t2.b;
}

void prep() {
    cin >> n;

    vector<pair<int, pair<int, int>>> v;
    for (int i = 1; i <= n; i ++) {
        cin >> tr[i].a >> tr[i].b >> tr[i].c >> tr[i].d;
        if (tr[i].a > tr[i].b) swap(tr[i].a, tr[i].b);
        if (tr[i].c > tr[i].d) swap(tr[i].c, tr[i].d);
        v.push_back({tr[i].c, {i, 1}});
        v.push_back({tr[i].d, {i, 2}});
    }

    //compress c and d
    sort(v.begin(), v.end());
    for (int i = 0; i < 2 * n; i ++) {
        if (v[i].second.second == 1) {
            tr[v[i].second.first].c = i + 1;
        } else {
            tr[v[i].second.first].d = i + 1;
        }
    }

    sort(tr + 1, tr + n + 1, cmp);

    ver[0] = build(1, 2 * n);
}

void solve() {
    for (int i = 1; i <= n; i ++) {
        // tim j max co tr[j].b < tr[i].a
        int s = 0, t = i - 1;
        while (s < t) {
            int mid = (s + t) / 2;
            if (tr[mid + 1].b < tr[i].a) s = mid + 1;
            else t = mid;
        }

        pair<int, int> ans = get(ver[s], 1, 2 * n, 1, tr[i].c - 1);
        dp[i] = ans.first + 1;
        dp_cnt[i] = ans.second;
        if (dp[i] == 1) dp_cnt[i] = 1;

        //cout << tr[i].a << " " << tr[i].b << " : " << dp[i] << " " << dp_cnt[i] << "\n";

        ver[i] = update(ver[i - 1], 1, 2 * n, tr[i].d, dp[i], dp_cnt[i]);
    }

    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= n; i ++) {
        if (dp[i] > ans1) {
            ans1 = dp[i];
            ans2 = dp_cnt[i];
        } else if (dp[i] == ans1) {
            ans2 += dp_cnt[i];
            ans2 %= mod;
        }
    }

    cout << ans1 << " " << ans2 << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    return 0;
}

• Subtask 1: 90 / 100