제출 #382620

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382620		peijar	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	127 ms	7640 KiB

trapezoid

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