제출 #376015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376015		peijar	Pinball (JOI14_pinball)	C++17	100 / 100	240 ms	19344 KiB

pinball

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

struct Segtree
{
	vector<int> seg;
	int nbFeuilles;
	const int UNDEF = 1e18;

	Segtree(int nbElem)
	{
		nbFeuilles = 1;
		while (nbFeuilles < nbElem) ++nbFeuilles;
		seg.assign(2 * nbFeuilles, UNDEF);
	}

	void update(int pos, int val)
	{
		pos += nbFeuilles;
		seg[pos] = min(seg[pos], val);
		while (pos > 1)
		{
			pos /= 2;
			seg[pos] = min(seg[2*pos], seg[2*pos+1]);
		}
	}

	int query(int deb, int fin)
	{
		int ans = UNDEF;
		deb += nbFeuilles, fin += nbFeuilles;
		while (deb < fin)
		{
			if (deb % 2)
				ans = min(ans, seg[deb]);
			if (fin%2==0)
				ans = min(ans, seg[fin]);
			deb = (deb + 1) / 2;
			fin = (fin - 1) / 2;
		}
		if (deb == fin)
			ans = min(ans, seg[deb]);
		return ans;
	}
};

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbLig, nbCol;
	cin >> nbLig >> nbCol;
	vector<int> valeurs;
	valeurs.push_back(1); valeurs.push_back(nbCol);
	vector<tuple<int, int ,int, int>> dispositifs(nbLig);
	for (auto &[deb, fin, trou, cout] : dispositifs)
	{
		cin >> deb >> fin >> trou >> cout;
		valeurs.push_back(deb);
		valeurs.push_back(fin);
		valeurs.push_back(trou);
	}
	sort(valeurs.begin(), valeurs.end());
	valeurs.resize(unique(valeurs.begin(), valeurs.end()) - valeurs.begin());

	auto calcInd = [&](int val)
	{
		return lower_bound(valeurs.begin(), valeurs.end(), val) - valeurs.begin();
	};

	Segtree segLeft(valeurs.size());
	Segtree segRight(valeurs.size());
	segLeft.update(calcInd(1), 0);
	segRight.update(calcInd(nbCol), 0);
	int sol(1e18);
	for (auto [deb, fin, trou, cout] : dispositifs)
	{
		deb = calcInd(deb);
		fin = calcInd(fin);
		trou = calcInd(trou);
		int queryLeft = segLeft.query(deb, fin);
		int queryRight = segRight.query(deb, fin);
		sol = min(sol, cout + queryLeft + queryRight);
		segLeft.update(trou, queryLeft + cout);
		segRight.update(trou, queryRight + cout);
	}
	if (sol == 1e18) sol = -1;
	cout << sol << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 49 / 49