Submission #1346140

#TimeUsernameProblemLanguageResultExecution timeMemory
1346140JahonaliXtrapezoid (balkan11_trapezoid)C++20
45 / 100
1096 ms5700 KiB
#include <bits/stdc++.h>

using namespace std;

#define int long long
constexpr int mod = 30013, inf = 1e17;

int32_t main() {
#ifdef JahonaliX
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, ans = 0, cn = 1;
    cin >> n;
    vector<int> a(n), b(n), c(n), d(n), dp(n, 1), cnt(n, 1), o(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> b[i] >> c[i] >> d[i];
    iota(o.begin(), o.end(), 0);
    sort(o.begin(), o.end(), [&] (int i, int j) { return a[i] < a[j]; });
    for (int i : o) {
        for (int j : o) {
            if (b[j] < a[i] && d[j] < c[i]) {
                if (dp[i] <= dp[j]) dp[i] = dp[j] + 1, cnt[i] = cnt[j];
                else if (dp[i] == dp[j] + 1) cnt[i] += cnt[j], cnt[i] %= mod;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        if (dp[i] > ans) ans = dp[i], cn = cnt[i];
        else if (dp[i] == ans) cn += cnt[i], cn %= mod;
    }
    cout << ans << ' ' << cn;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...