Submission #39768

#	Time	Username	Problem	Language	Result	Execution time	Memory
39768		krauch	trapezoid (balkan11_trapezoid)	C++14	45 / 100	500 ms	6708 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size();
#define all(a) a.begin(), a.end()

const int N = 2e5 + 6, base = 30013;

struct trap {
    int ul, ur, dl, dr;
    trap(){}
} a[N];


int n;
PII d[N];

bool cmp(trap a, trap b) {
    return a.ul < b.ul;
}

int main() {

    cin >> n;
    forn(i, 1, n) {
        cin >> a[i].ul >> a[i].ur >> a[i].dl >> a[i].dr;
    }

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

    int mx = 0;
    forn(i, 1, n) {
        d[i] = PII(1, 1);
        forn(j, 1, i - 1) {
            if (!(a[j].ur < a[i].ul && a[j].dr < a[i].dl) || d[j].S < d[i].S - 1) continue;
            if (d[j].S > d[i].S - 1) {
                d[i].F = d[j].F;
                d[i].S = d[j].S + 1;
            }
            else d[i].F = (d[j].F + d[i].F) % base;
        }
        mx = max(mx, d[i].S);
    }

    int ans = 0;
    forn(i, 1, n) if (d[i].S == mx) ans = (ans + d[i].F) % base;

    cout << mx << " " << ans << "\n";

    return 0;
}

• Subtask 1: 45 / 100