Submission #383334

#	Time	Username	Problem	Language	Result	Execution time	Memory
383334		peijar	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	34 / 100	3050 ms	92780 KiB

sortbooks

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

struct Requete
{
	int deb, fin, patience, iRequete;

	bool operator<(Requete other) const
	{
		return patience < other.patience;
	}
};

const int NB_FEUILLES = 1 << 20;

int seg[2 * NB_FEUILLES];

void init()
{
	for (int i(0); i < 2 * NB_FEUILLES; ++i) seg[i]= -1;
}

void upd(int iPos, int val)
{
	iPos += NB_FEUILLES;
	seg[iPos] = val;
	while (iPos > 1)
	{
		iPos /= 2;
		seg[iPos] = max(seg[2*iPos], seg[2*iPos+1]);
	}
}

int query(int deb, int fin)
{
	deb += NB_FEUILLES, fin += NB_FEUILLES;
	int sol(-1);
	while (deb < fin)
	{
		if (deb % 2)
			sol = max(sol, seg[deb++]);
		if (fin%2==0)
			sol = max(sol, seg[fin--]);
		deb /= 2; fin /= 2;
	}
	if (deb == fin) sol = max(sol, seg[deb]);
	return sol;
}

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

	int nbLivres, nbRequetes;
	cin >> nbLivres >> nbRequetes;
	vector<int> poids(nbLivres);
	for (auto &v : poids) cin >> v;
	vector<Requete> requetes(nbRequetes);
	for (int iRequete = 0; iRequete < nbRequetes; ++iRequete) 
	{
		auto &r = requetes[iRequete];
		cin >> r.deb >> r.fin >> r.patience;
		r.deb--, r.fin--;
		r.iRequete = iRequete;
	}
	sort(requetes.begin(), requetes.end());
	vector<int> lft(nbLivres);
	for (int iLivre = 0; iLivre < nbLivres; ++iLivre) 
	{
		lft[iLivre] = iLivre-1;
		while (lft[iLivre] != -1 and poids[lft[iLivre]] <= poids[iLivre])
			lft[iLivre] = lft[lft[iLivre]];
	}
	vector<pair<int, int>> aAjouter;
	for (int iLivre = 0; iLivre < nbLivres; ++iLivre) 
		if (lft[iLivre] != -1)
			aAjouter.emplace_back(poids[iLivre] + poids[lft[iLivre]], iLivre);
	sort(aAjouter.begin(), aAjouter.end());
	init();
	vector<bool> solRequete(nbRequetes);
	vector<int> curVal(nbLivres, -1);
	for (int iRequete(nbRequetes-1); iRequete >= 0; --iRequete)
	{
		while (!aAjouter.empty() and aAjouter.back().first > requetes[iRequete].patience)
		{
			upd(aAjouter.back().second, lft[aAjouter.back().second]);
			curVal[aAjouter.back().second] = lft[aAjouter.back().second];
			aAjouter.pop_back();
		}
		int ret = 1;
		for (int i(requetes[iRequete].deb); i <= requetes[iRequete].fin; ++i)
			if (curVal[i] >= requetes[iRequete].deb)
			{
				ret = 0;
				break;
			}
		solRequete[requetes[iRequete].iRequete] = query(requetes[iRequete].deb, requetes[iRequete].fin) < requetes[iRequete].deb;
		assert(ret == solRequete[requetes[iRequete].iRequete]);
	}
	for (auto v : solRequete)
		cout << (v  ? 1 : 0) << '\n';
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23