Submission #1128001

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128001		Mikael639	trapezoid (balkan11_trapezoid)	C++20	10 / 100	1096 ms	2536 KiB

trapezoid

#include <bits/stdc++.h>

#define fi first
#define se second

#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define ForD(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repD(i, n) for (int i = (n) - 1; i >= 0; --i)
#define coutE(x) {cout << x << '\n'; return;}
#define pb push_back
#define pf push_front

#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define bs binary_search
#define ub upper_bound
#define lb lower_bound

#define endl '\n'

#define db long double
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<ii>

using namespace std;

template <class X, class Y>
	bool minimize(X &x, Y y){
		if (x > y) return x = y, 1;
		return 0;
	}

template <class X, class Y>
	bool maximize(X &x, Y y){
		if (x < y) return x = y, 1;
		return 0;
	}

const int N = 1e5 + 5;
const int MOD = 30013;

int n, a[N], b[N], c[N], d[N];
ii dp[N];
int p[N];

void add(int &x, int y){
    x += y;
    if (x >= MOD) x -= MOD;
}

void upd(ii &x, ii y){
    if (maximize(x.fi, y.fi))
        x.se = y.se;
    else if (x.fi == y.fi)
        add(x.se, y.se);
}

bool ok(int i, int j){
    if (a[i] <= a[j] && a[j] <= b[i]) return 0;
    if (a[i] <= b[j] && b[j] <= b[i]) return 0;
    if (a[j] <= a[i] && a[i] <= b[j]) return 0;
    if (a[j] <= b[i] && b[i] <= b[j]) return 0;

    if (c[i] <= c[j] && c[j] <= d[i]) return 0;
    if (c[i] <= d[j] && d[j] <= d[i]) return 0;
    if (c[j] <= c[i] && c[i] <= d[j]) return 0;
    if (c[j] <= d[i] && d[i] <= d[j]) return 0;

    return 1;
}

signed main(){

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

    cin >> n;
    For(i, 1, n){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
    }

    iota(p + 1, p + n + 1, 1);
    sort(p + 1, p + n + 1, [&](int i, int j){
        return min(a[i], c[i]) < min(a[j], c[j]);
    });

    ii res = {0, 1};
    For(i, 1, n){
        dp[i] = {1, 1};
        For(j, 1, i - 1) if (ok(i, j)){
            ii tmp = dp[j];
            ++tmp.fi;
            upd(dp[i], tmp);
        }
        upd(res, dp[i]);
    }

    cout << res.fi << ' ' << res.se;

	return 0;
}

• Subtask 1: 10 / 100