Submission #382619

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
382619	2021-03-27T22:16:52 Z	peijar	trapezoid (balkan11_trapezoid)	C++17	100 / 100	138 ms	17356 KB

trapezoid

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

const int MOD = 30013;

pair<int, int> merge(pair<int, int> lhs, pair<int, int> rhs)
{
	auto [ml, cl] = lhs;
	auto [mr, cr] = rhs;
	if (ml < mr)
		return rhs;
	if (ml > mr)
		return lhs;
	return make_pair(ml, (cl + cr) % MOD);
}

struct Fen
{
	int N;
	vector<pair<int, int>> bit;

	
	Fen(int n) : N(n+1), bit(N, make_pair(0, 0)){	}

	void set(int x, pair<int, int> val)
	{
		for (x++; x < N; x += x & -x)
			bit[x] = merge(bit[x], val);
	}

	pair<int, int> getBest(int r) // < r
	{
		pair<int, int> ret(0, 0);
		for (; r; r -= r & -r)
			ret = merge(bit[r], ret);
		return ret;
	}
};

struct Trapeze
{
	int uDeb, uFin, lDeb, lFin;
};

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int nbTrapezes;
	cin >> nbTrapezes;
	vector<Trapeze> trapezes(nbTrapezes);
	vector<int> valLo, valUp;
	for (auto &[uDeb, uFin, lDeb, lFin] : trapezes)
	{
		cin >> uDeb >> uFin >> lDeb >> lFin;
		valLo.push_back(lDeb); valLo.push_back(lFin);
		valUp.push_back(uDeb); valUp.push_back(uFin);
	}
	sort(valLo.begin(), valLo.end());
	sort(valUp.begin(), valUp.end());
	for (auto &[uDeb, uFin, lDeb, lFin] : trapezes)
	{
		uDeb = lower_bound(valUp.begin(), valUp.end(), uDeb) - valUp.begin()+1;	
		uFin = lower_bound(valUp.begin(), valUp.end(), uFin) - valUp.begin()+1;	
		lDeb = lower_bound(valLo.begin(), valLo.end(), lDeb) - valLo.begin()+1;	
		lFin = lower_bound(valLo.begin(), valLo.end(), lFin) - valLo.begin()+1;	
	}
	Fen fen(2 * nbTrapezes+1);
	fen.set(0, make_pair(0, 1));
	vector<pair<int, int>> event(2*nbTrapezes+1);
	for (int iTrapeze = 0; iTrapeze < nbTrapezes; ++iTrapeze) 
	{
		event[trapezes[iTrapeze].lDeb] = make_pair(iTrapeze, 1);
		event[trapezes[iTrapeze].lFin] = make_pair(iTrapeze, -1);
	}

	vector<pair<int, int>> dp(nbTrapezes);
	
	for (int iPos = 1; iPos < 2 * nbTrapezes+1; ++iPos) 
	{
		auto [iTrapeze, type] = event[iPos];
		if (type == 1)
		{
			dp[iTrapeze] = fen.getBest(trapezes[iTrapeze].uDeb);
			dp[iTrapeze].first++;
		}
		else
			fen.set(trapezes[iTrapeze].uFin, dp[iTrapeze]);
	}
	pair<int, int> sol(0, 0);
	for (auto u : dp)
		sol = merge(sol, u);
	cout << sol.first << ' ' << sol.second << endl;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	312 KB	Output is correct
3	Correct	2 ms	400 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	3 ms	748 KB	Output is correct
6	Correct	4 ms	876 KB	Output is correct
7	Correct	5 ms	1004 KB	Output is correct
8	Correct	7 ms	1260 KB	Output is correct
9	Correct	13 ms	2024 KB	Output is correct
10	Correct	25 ms	3936 KB	Output is correct
11	Correct	31 ms	4832 KB	Output is correct
12	Correct	66 ms	8920 KB	Output is correct
13	Correct	81 ms	10712 KB	Output is correct
14	Correct	98 ms	12496 KB	Output is correct
15	Correct	109 ms	13136 KB	Output is correct
16	Correct	117 ms	14060 KB	Output is correct
17	Correct	121 ms	15056 KB	Output is correct
18	Correct	115 ms	15820 KB	Output is correct
19	Correct	125 ms	16756 KB	Output is correct
20	Correct	138 ms	17356 KB	Output is correct