oj.uz

Submission #382620

# Submission time Handle Problem Language Result Execution time Memory
382620 2021-03-27T22:17:57 Z peijar trapezoid (balkan11_trapezoid) C++17
100 / 100
 127 ms 7640 KB 
#include <bits/stdc++.h>
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 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 3 ms 492 KB Output is correct
6 Correct 4 ms 620 KB Output is correct
7 Correct 7 ms 620 KB Output is correct
8 Correct 6 ms 748 KB Output is correct
9 Correct 12 ms 1132 KB Output is correct
10 Correct 23 ms 1768 KB Output is correct
11 Correct 35 ms 2152 KB Output is correct
12 Correct 60 ms 4064 KB Output is correct
13 Correct 74 ms 4832 KB Output is correct
14 Correct 87 ms 5464 KB Output is correct
15 Correct 97 ms 5848 KB Output is correct
16 Correct 109 ms 6348 KB Output is correct
17 Correct 115 ms 6744 KB Output is correct
18 Correct 108 ms 7000 KB Output is correct
19 Correct 115 ms 7256 KB Output is correct
20 Correct 127 ms 7640 KB Output is correct