Submission #251789

#	Time	Username	Problem	Language	Result	Execution time	Memory
251789		tutis	trapezoid (balkan11_trapezoid)	C++17	45 / 100	1095 ms	13304 KiB

trapezoid

/*input
7
1 3 1 9
4 7 2 8
11 15 4 12
10 12 15 19
16 23 16 22
20 22 13 25
30 31 30 31
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename K>
using ordered_map = tree<T, K, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int a[n + 1], b[n + 1], c[n + 1], d[n + 1];
	for (int i = 0; i < n; i++)
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	a[n] = c[n] = 1e9 + 50;
	b[n] = d[n] = a[n] + 50;
	n++;
	{
		map<int, int>M;
		for (int i = 0; i < n; i++)
			M[a[i]] = M[b[i]] = 0;
		int t = 0;
		for (auto &x : M)
			x.second = ++t;
		for (int i = 0; i < n; i++) {
			a[i] = M[a[i]];
			b[i] = M[b[i]];
		}
	}
	{
		map<int, int>M;
		for (int i = 0; i < n; i++)
			M[c[i]] = M[d[i]] = 0;
		int t = 0;
		for (auto &x : M)
			x.second = ++t;
		for (int i = 0; i < n; i++) {
			c[i] = M[c[i]];
			d[i] = M[d[i]];
		}
	}
	int p[n];
	iota(p, p + n, 0);
	sort(p, p + n, [&](int x, int y) {return a[x] < a[y];});
	pair<int, int>dp[n];
	for (int i = 0; i < n; i++)
	{
		dp[i] = {1, 1};
		for (int j = 0; j < i; j++)
		{
			if (b[p[j]] < a[p[i]] && d[p[j]] < c[p[i]])
			{
				int kiek = dp[j].first + 1;
				if (kiek >= dp[i].first)
				{
					if (kiek > dp[i].first)
						dp[i].second = 0;
					dp[i].first = kiek;
					dp[i].second += dp[j].second;
					if (dp[i].second >= 30013)
						dp[i].second -= 30013;
				}
			}
		}
	}
	cout << dp[n - 1].first - 1 << " " << dp[n - 1].second << "\n";
	return 0;
}

• Subtask 1: 45 / 100