oj.uz

Submission #815252

# Submission time Handle Problem Language Result Execution time Memory
815252 2023-08-08T13:32:38 Z acatmeowmeow trapezoid (balkan11_trapezoid) C++11
62 / 100
 73 ms 4528 KB 
#include <bits/stdc++.h>

using namespace std;

//#define int long long 

const int N = 1e5, modulo = 30013;
int n, a[N + 5], b[N + 5], c[N + 5], d[N + 5];
pair<int, int> indx[N + 5], tree[2*N + 5], dp[N + 5];
vector<int> mp;

pair<int, int> combine(pair<int, int>&f, pair<int, int>&se) {
	if (f.first == se.first) return {f.first, (f.second + se.second) % modulo};
	else return f > se ? f : se;
}

void update(int k, pair<int, int> x) {
	for (; k <= 2*n; k += k&-k) tree[k] = combine(tree[k], x);
}

pair<int, int> query(int k) {
	pair<int, int> ans = {0, 0};
	for (; k; k -= k&-k) ans = combine(ans, tree[k]);
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i] >> b[i] >> c[i] >> d[i];

	for (int i = 1; i <= 2*n; i += 2) indx[i] = {(i + 1)/2, 0}, indx[i + 1] = {(i + 1)/2, 1};
	sort(indx + 1, indx + 2*n + 1, [&](pair<int, int>&x, pair<int, int>&y) {
			int f = x.second == 0 ? a[x.first] : b[x.first];
			int se = y.second == 0 ? a[y.first] : b[y.first];
			return f < se;
	});

	for (int i = 1; i <= n; i++) mp.push_back(c[i]), mp.push_back(d[i]);
	sort(mp.begin(), mp.end());
	mp.erase(unique(mp.begin(), mp.end()), mp.end());
	auto getIndex = [&](int p) { return lower_bound(mp.begin(), mp.end(), p) - mp.begin() + 1; };

	for (int i = 1; i <= 2*n; i++) {
		int index = indx[i].first, type = indx[i].second;
		if (!type) {
			int Y = getIndex(c[index]);
			pair<int, int> res = query(Y);
			if (!res.first) dp[index] = {1, 1};
			else dp[index] = {res.first + 1, res.second};
		} else {
			int Y = getIndex(d[index]);
			update(Y, dp[index]);
		}
	}
	int mx = 0, total = 0;
	for (int i = 1; i <= n; i++) {
		if (mx < dp[i].first) mx = dp[i].first, total = dp[i].second;
		else if (mx == dp[i].first) total += dp[i].second, total %= modulo;
	}
	cout << mx << " "<< total << '\n';
	return 0;
}

Subtask #1
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 8 ms 1056 KB Output is correct
10 Correct 15 ms 1680 KB Output is correct
11 Correct 19 ms 2004 KB Output is correct
12 Correct 41 ms 3584 KB Output is correct
13 Incorrect 47 ms 3712 KB Output isn't correct
14 Incorrect 54 ms 3648 KB Output isn't correct
15 Incorrect 62 ms 3832 KB Output isn't correct
16 Incorrect 62 ms 4040 KB Output isn't correct
17 Incorrect 63 ms 4092 KB Output isn't correct
18 Partially correct 63 ms 4228 KB Partially correct
19 Incorrect 63 ms 4408 KB Output isn't correct
20 Incorrect 73 ms 4528 KB Output isn't correct