oj.uz

Submission #376014

# Submission time Handle Problem Language Result Execution time Memory
376014 2021-03-10T16:44:44 Z peijar Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 364 KB 
#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());
	for (auto v : valeurs)
		cout << v << ' ';
	cout << endl;

	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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -