Submission #375626

#	Time	Username	Problem	Language	Result	Execution time	Memory
375626		peijar	Examination (JOI19_examination)	C++17	100 / 100	641 ms	47768 KiB

examination

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

struct CountLess
{
	vector<int> values;
	vector<vector<int>> seg;
	vector<int> iDeb, iFin;

	CountLess(const vector<int> &_values) : values(_values)
	{
		int p(0);
		while ((1 << p) < (int)values.size()) ++p;
		seg.resize((1 << (p+1))+1);
		iDeb.resize((1 <<(p+1))+1);
		iFin.resize((1<<(p+1))+1);
		build(1, 0, (int)values.size() - 1);
	};

	void build(int iNoeud, int deb, int fin)
	{
		iDeb[iNoeud] = deb;
		iFin[iNoeud] = fin;
		if (deb == fin)
		{
			seg[iNoeud] = {values[deb]};
			return ;
		}
		build(2*iNoeud, deb, (deb+fin)/2);
		build(2*iNoeud+1, (deb+fin)/2+1, fin);
		seg[iNoeud].resize(seg[2*iNoeud].size() + seg[2*iNoeud+1].size());
		merge(seg[2*iNoeud].begin(), seg[2*iNoeud].end(),
												seg[2*iNoeud+1].begin(), seg[2*iNoeud+1].end(),
												seg[iNoeud].begin());
	}

	int countGreater(int iNoeud, int iDebR, int iFinR, int borne)
	{
		if (iFinR < iDeb[iNoeud] or iDebR > iFin[iNoeud])
			return 0;
		if (iDeb[iNoeud] >= iDebR and iFin[iNoeud] <= iFinR)
		{
			int pos = lower_bound(seg[iNoeud].begin(), seg[iNoeud].end(), borne)
				- seg[iNoeud].begin();
			return (int)seg[iNoeud].size() - pos;
		}
		return countGreater(2*iNoeud, iDebR, iFinR, borne)
			+ countGreater(2*iNoeud+1, iDebR, iFinR, borne);
	}
};

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

	int nbEleves, nbRequetes;
	cin >> nbEleves >> nbRequetes;
	vector<pair<int, int>> notes(nbEleves);
	for (auto &[noteMaths, noteInfo] : notes)
		cin >> noteMaths >> noteInfo;
	sort(notes.begin(), notes.end());

	vector<int> notesInfo(nbEleves);
	vector<int> sommeNotes(nbEleves);
	for (int i(0); i < nbEleves; ++i)
	{
		notesInfo[i] = notes[i].second;
		sommeNotes[i] = notes[i].first + notes[i].second;
	}

	CountLess countInfo(notesInfo), countSomme(sommeNotes);
	for (int iRequete(0); iRequete < nbRequetes; ++iRequete)
	{
		int mathsMin, infoMin, sommeMin;
		cin >> mathsMin >> infoMin >> sommeMin;
		int posDepart = lower_bound(notes.begin(), notes.end(), make_pair(mathsMin, 0)) - notes.begin();
		// info >= infoMin et info >= sommeMin - maths
		// sommeMin - maths >= infoMin <=> maths <= sommeMin - infoMin
		int posDebInfo = upper_bound(notes.begin(), notes.end(), make_pair(sommeMin-infoMin, -1)) - notes.begin();
		if (posDebInfo < posDepart) posDebInfo = posDepart;
		int ret(0);
		if (posDepart < posDebInfo)
			ret += countSomme.countGreater(1, posDepart, posDebInfo-1, sommeMin);
		if (posDebInfo < nbEleves)
			ret += countInfo.countGreater(1, posDebInfo, nbEleves-1, infoMin);
		cout << ret << '\n';
	}
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57