Submission #541136

#	Time	Username	Problem	Language	Result	Execution time	Memory
541136		akhan42	trapezoid (balkan11_trapezoid)	C++17	30 / 100	837 ms	65536 KiB

trapezoid

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define F first
#define S second
#define forn(i, n) for(int i = 0; i < n; ++i)
#define forbn(i, b, n) for(int i = b; i < n; ++i)
#define sz(v) (int)v.size()
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b, c))

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long long ll;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

template <class T> inline void mineq(T &a, T b) { a = min(a, b); }
template <class T> inline void maxeq(T &a, T b) { a = max(a, b); }


const int MX = 5005;
int bl[MX], br[MX], ul[MX], ur[MX];
vi gr[MX];
vi gr2[MX];
int dep[MX];
vector<bool> att;
bool att2[MX][MX];
int paths[MX][MX];
int mod = 30013;


int add(int a, int b) {
	return (a + b) % mod;
}


void addm(int& a, int b) {
	a = (a + b) % mod;
}


void dfs(int i) {
	att[i] = true;
	for(int nb: gr[i]) {
		if(!att[nb])
			dfs(nb);
		maxeq(dep[i], dep[nb] + 1);
	}
}


int dfs2(int i, int d) {
	if(att2[i][d])
		return paths[i][d];

	att2[i][d] = true;
	if(d == 0)
		paths[i][d] = 1;

	for(int nb: gr2[i]) {
		addm(paths[i][d], dfs2(nb, d - 1));

		maxeq(dep[i], dep[nb] + 1);
	}

	return paths[i][d];
}


void solve() {
	int n;
	cin >> n;
	forn(i, n) {
		cin >> ul[i] >> ur[i] >> bl[i] >> br[i];
	}

	forn(i, n) {
		forn(j, n) {
			if(i == j) continue;
			if(ur[i] < ul[j] && br[i] < bl[j]) {
				gr[j].pb(i);
				gr2[i].pb(j);
			}
		}
	}

	att.assign(MX, false);
	forn(i, n) {
		if(!att[i]) {
			dfs(i);
		}
	}
	int mxd = 0;
	forn(i, n) {
		maxeq(mxd, dep[i]);
		dep[i] = 0;
	}

	forn(i, n) {
		dfs2(i, mxd);
	}

	int ans = 0;
	forn(i, n) {
		addm(ans, paths[i][mxd]);
	}

	cout << mxd + 1 << ' ' << ans << '\n';
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

//	freopen("slingshot.in", "r", stdin);
//	freopen("slingshot.out", "w", stdout);

	int t = 1;
//	cin >> t;
	while(t--) {
		solve();
	}
}

• Subtask 1: 30 / 100