Submission #1265917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265917		canhnam357	trapezoid (balkan11_trapezoid)	C++20	100 / 100	126 ms	20920 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define MASK(i) (1LL << (i))
#define int long long
const int inf = 2e9;
const int mod = 3e4 + 13;
const int N = 2.5e5 + 5;
const int b = 1500;
void ckmax(int& f, int s)
{
	f = (f > s ? f : s);
}
void ckmin(int& f, int s)
{
	f = (f < s ? f : s);
}
bool cp(tuple<int, int, int, int> a, tuple<int, int, int, int> b)
{
	return get<1>(a) < get<1>(b);
}
bool cp2(tuple<int, int, int> a, tuple<int, int, int> b)
{
	if (get<0>(a) == get<0>(b)) return get<1>(a) > get<1>(b);
	return get<0>(a) < get<0>(b);
}
pair<int, int> st[1 << 19];
pair<int, int> operator+(pair<int, int> a, pair<int, int> b)
{
	if (a.first == b.first) return {a.first, (a.second + b.second) % mod};
	return max(a, b);
}
void build(int id = 1, int l = 1, int r = 1 << 18)
{
	if (l == r)
	{
		st[id] = {0, 1};
		return;
	}
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int pos, pair<int, int> val, int id = 1, int l = 1, int r = 1 << 18)
{
	if (pos < l || pos > r) return;
	if (l == r)
	{
		if (val.first == st[id].first) (st[id].second += val.second) %= mod;
		else if (val.first > st[id].first) st[id] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(pos, val, id << 1, l, mid);
	update(pos, val, id << 1 | 1, mid + 1, r);
	st[id] = st[id << 1] + st[id << 1 | 1];
}
pair<int, int> get(int u, int v, int id = 1, int l = 1, int r = 1 << 18)
{
	if (r < u || l > v) return {0, 0};
	if (l >= u && r <= v) return st[id];
	int mid = (l + r) >> 1;
	auto gl = get(u, v, id << 1, l, mid);
	auto gr = get(u, v, id << 1 | 1, mid + 1, r);
	if (gl.first == gr.first) return {gl.first, (gl.second + gr.second) % mod};
	return max(gl, gr);
}
void solve()
{
	build();
	int n;
	cin >> n;
	vector<tuple<int, int, int, int>> v(n);
	vector<int> cc;
	for (auto &[a, b, c, d] : v) cin >> a >> b >> c >> d, cc.push_back(c), cc.push_back(d);
	sort(all(cc));
	cc.erase(unique(all(cc)), cc.end());
	auto get_pos = [&](int val)
	{
		return upper_bound(all(cc), val) - cc.begin();
	};
	for (auto &[a, b, c, d] : v)
	{
		c = get_pos(c);
		d = get_pos(d);
	}
	sort(all(v), cp);
	vector<tuple<int, int, int>> s;
	for (int i = 0; i < n; i++)
	{
		auto [a, b, c, d] = v[i];
		s.emplace_back(a, c, i + 1);
		s.emplace_back(b, d, -(i + 1));
	}
	sort(all(s));
	vector<pair<int, int>> u(n);
	for (auto [t, b, id] : s)
	{
		if (id < 0)
		{
			id = -id - 1;
			update(get<3>(v[id]), u[id]);
		}
		else
		{
			id = id - 1;
			auto k = get(1, get<2>(v[id]) - 1);
			k.first++;
			if (k.first == 1) k.second = 1;
			u[id] = k;
		}
	}
	cout << st[1].first << ' ' << st[1].second;
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	while (t--) solve();
	return 0;
}

• Subtask 1: 100 / 100