oj.uz

답안 #815268

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
815268 2023-08-08T13:39:26 Z acatmeowmeow 사다리꼴 (balkan11_trapezoid) C++11
100 / 100
 84 ms 6760 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[2*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
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 4 ms 724 KB Output is correct
9 Correct 9 ms 1204 KB Output is correct
10 Correct 15 ms 1880 KB Output is correct
11 Correct 19 ms 2164 KB Output is correct
12 Correct 41 ms 3716 KB Output is correct
13 Correct 50 ms 4364 KB Output is correct
14 Correct 61 ms 4896 KB Output is correct
15 Correct 67 ms 5260 KB Output is correct
16 Correct 71 ms 5576 KB Output is correct
17 Correct 74 ms 5800 KB Output is correct
18 Correct 67 ms 6168 KB Output is correct
19 Correct 73 ms 6340 KB Output is correct
20 Correct 84 ms 6760 KB Output is correct