Submission #1255903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255903		ssitaram	trapezoid (balkan11_trapezoid)	C++20	100 / 100	77 ms	6588 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int MOD = 30013;

struct trap {
	int a, b, c, d;
};

struct segtree {
	int n;
	vector<pair<int, int>> here;

	segtree(int sz) {
		n = 1;
		while (n < sz) n *= 2;
		here.resize(2 * n - 1);
	}

	pair<int, int> comb(pair<int, int>& a, pair<int, int>& b) {
		if (a.first < b.first) return b;
		if (a.first > b.first) return a;
		return {a.first, (a.second + b.second) % MOD};
	}

	void upd(int node, int l, int r, int u, pair<int, int>& p) {
		if (r == l + 1) {
			here[node] = p;
			return;
		}
		int m = (l + r) / 2;
		if (u < m) upd(node * 2 + 1, l, m, u, p);
		else upd(node * 2 + 2, m, r, u, p);
		here[node] = comb(here[node * 2 + 1], here[node * 2 + 2]);
	}

	void upd(int u, pair<int, int>& p) { upd(0, 0, n, u, p); }

	pair<int, int> over(int node, int l, int r, int u) {
		if (r <= u) return here[node];
		if (l >= u) return {0, 0};
		int m = (l + r) / 2;
		pair<int, int> one = over(node * 2 + 1, l, m, u);
		pair<int, int> two = over(node * 2 + 2, m, r, u);
		return comb(one, two);
	}

	pair<int, int> over(int u) { return over(0, 0, n, u); }
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<int> to(n);
	vector<trap> v(n);
	vector<pair<int, int>> order;
	for (int i = 0; i < n; ++i) {
		cin >> v[i].a >> v[i].b >> v[i].c >> v[i].d;
		to[i] = v[i].b;
		order.push_back({v[i].c, i});
		order.push_back({v[i].d, i});
	}
	vector<pair<int, int>> ans(n);
	sort(to.begin(), to.end());
	sort(order.begin(), order.end());
	segtree st(n);
	for (pair<int, int>& i : order) {
		if (v[i.second].d == i.first) {
			st.upd(lower_bound(to.begin(), to.end(), v[i.second].b) - to.begin(), ans[i.second]);
		} else {
			ans[i.second] = st.over(lower_bound(to.begin(), to.end(), v[i.second].a) - to.begin());
			if (++ans[i.second].first == 1) ans[i.second].second = 1;
		}
	}
	pair<int, int> res = st.over(n);
	cout << res.first << ' ' << res.second << '\n';
	return 0;
}

• Subtask 1: 100 / 100