oj.uz

Submission #541136

# Submission time Handle Problem Language Result Execution time Memory
541136 2022-03-22T10:56:52 Z akhan42 trapezoid (balkan11_trapezoid) C++17
30 / 100
 500 ms 65536 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 12 ms 5696 KB Output is correct
4 Correct 107 ms 13752 KB Output is correct
5 Correct 154 ms 32704 KB Output is correct
6 Execution timed out 837 ms 64948 KB Time limit exceeded
7 Runtime error 140 ms 65536 KB Execution killed with signal 9
8 Correct 179 ms 61200 KB Output is correct
9 Runtime error 5 ms 1328 KB Execution killed with signal 11
10 Runtime error 5 ms 1492 KB Execution killed with signal 11
11 Runtime error 5 ms 1424 KB Execution killed with signal 11
12 Runtime error 5 ms 1400 KB Execution killed with signal 11
13 Runtime error 5 ms 1468 KB Execution killed with signal 11
14 Runtime error 5 ms 1492 KB Execution killed with signal 11
15 Runtime error 6 ms 1492 KB Execution killed with signal 11
16 Runtime error 7 ms 1484 KB Execution killed with signal 11
17 Runtime error 5 ms 1484 KB Execution killed with signal 11
18 Runtime error 5 ms 1480 KB Execution killed with signal 11
19 Runtime error 5 ms 1364 KB Execution killed with signal 11
20 Runtime error 7 ms 1492 KB Execution killed with signal 11