Submission #889316

#TimeUsernameProblemLanguageResultExecution timeMemory
889316borisAngelovtrapezoid (balkan11_trapezoid)C++17
15 / 100
1068 ms5520 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 100005; const int mod = 30013; int n; struct Segment { int x; int y; }; bool cross(const Segment& fr, const Segment& sc) { return fr.x <= sc.y && fr.y >= sc.x; } struct Trapezoid { Segment up; Segment down; }; Trapezoid a[maxn]; pair<int, int> dp[maxn]; void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i].up.x >> a[i].up.y >> a[i].down.x >> a[i].down.y; } for (int i = 1; i <= n; ++i) { dp[i].first = 1; dp[i].second = 1; for (int j = i - 1; j >= 1; --j) { if (cross(a[i].down, a[j].down) == false && cross(a[i].up, a[j].up) == false && !((a[i].down.y < a[j].down.x && a[i].up.x > a[j].up.y) || (a[i].down.x > a[j].down.y && a[j].up.x > a[i].up.y))) { //cout << i << ' ' << j << endl; if (dp[i].first < 1 + dp[j].first) { dp[i].first = 1 + dp[j].first; dp[i].second = dp[j].second; } else if (dp[i].first == 1 + dp[j].first) { dp[i].second += dp[j].second; if (dp[i].second >= mod) { dp[i].second -= mod; } } } } } int mx = 0; int cnt = 0; for (int i = 1; i <= n; ++i) { if (mx < dp[i].first) { mx = dp[i].first; cnt = dp[i].second; } else if (mx == dp[i].first) { cnt += dp[i].second; if (cnt >= mod) { cnt -= mod; } } } cout << mx << ' ' << cnt << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...