Submission #815268

#	Time	Username	Problem	Language	Result	Execution time	Memory
815268		acatmeowmeow	trapezoid (balkan11_trapezoid)	C++11	100 / 100	84 ms	6760 KiB

trapezoid

#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 / 100