Submission #1221185

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221185		takoshanava	trapezoid (balkan11_trapezoid)	C++20	100 / 100	335 ms	58288 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 N = 1e5 + 5, MOD = 30013;

int n, T;
int a[N], b[N], c[N], d[N];
pair<int, int> dp[N], bs = {0, 0}, v[16 * N];
vector<int> U[4 * N], G[4 * N];

void compress() {
    vector<int> s;
    map<int, int> f;
    for (int i = 1; i <= n; i++) {
        s.pb(a[i]); s.pb(b[i]); s.pb(c[i]); s.pb(d[i]);
    }
    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());
    T = s.size();
    for (int i = 0; i < T; i++) f[s[i]] = i + 1;
    for (int i = 1; i <= n; i++) {
        a[i] = f[a[i]];
        b[i] = f[b[i]];
        c[i] = f[c[i]];
        d[i] = f[d[i]];
    }
}

pair<int, int> comb(pair<int, int> A, pair<int, int> B) {
    pair<int, int> res;
    res.fs = max(A.fs, B.fs);
    res.sc = 0;
    if (res.fs == A.fs) res.sc = (res.sc + A.sc) % MOD;
    if (res.fs == B.fs) res.sc = (res.sc + B.sc) % MOD;
    return res;
}

void upd(int h, int l, int r, int id, pair<int, int> val) {
    if (id < l || r < id) return;
    if (l == r) {
        if (v[h].fs == val.fs) v[h].sc = (v[h].sc + val.sc) % MOD;
        else v[h] = val;
        return;
    }
    int m = (l + r) / 2;
    upd(h * 2, l, m, id, val);
    upd(h * 2 + 1, m + 1, r, id, val);
    v[h] = comb(v[h * 2], v[h * 2 + 1]);
}

pair<int, int> get(int h, int l, int r, int L, int R) {
    if (r < L or R < l) return bs;
    if (L <= l and r <= R) return v[h];
    int m = (l + r) / 2;
    return comb(get(h * 2, l, m, L, R), get(h * 2 + 1, m + 1, r, L, R));
}

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];

    compress();

    for (int i = 1; i <= n; i++) {
        U[b[i]].pb(i);
        G[a[i]].pb(i);
    }

    for (int i = 1; i <= T; i++) {
        for (int j = 0; j < G[i].size(); ++j) {
            int id = G[i][j];
            pair<int, int> res = get(1, 1, T, 1, c[id] - 1);
            if (!res.sc) res.sc = 1;
            res.fs++;
            dp[id] = res;
        }
        for (int j = 0; j < U[i].size(); ++j) {
            int id = U[i][j];
            upd(1, 1, T, d[id], dp[id]);
        }
    }

    cout << v[1].fs << " " << v[1].sc << endl;
}

• Subtask 1: 100 / 100