제출 #376379

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376379		peijar	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	245 ms	44672 KiB

fortune_telling2

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


struct countGreater
{
	vector<vector<int>> seg;
	vector<int> deb, fin;
	vector<int> valeurs;

	countGreater(const vector<int> &v) : valeurs(v)
	{
		int nbElem(1);
		while (nbElem < (int)v.size())
			nbElem *= 2;
		seg.resize(2 * nbElem), deb.resize(2*nbElem), fin.resize(2*nbElem);
		build(1, 0, (int)v.size()-1);
	}

	void build(int iNoeud, int iDeb, int iFin)
	{
		deb[iNoeud] = iDeb, fin[iNoeud] = iFin;
		if (iDeb == iFin)
		{
			seg[iNoeud] = {valeurs[iDeb]};
			return ;
		}
		int iMid = (iDeb + iFin) / 2;
		build(2*iNoeud, iDeb, iMid);
		build(2*iNoeud+1, iMid+1, iFin);
		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());
	}

	bool query(int iNoeud, int debR, int finR, int borne)
	{
		if (debR > fin[iNoeud] or finR < deb[iNoeud])
			return 0;
		if (debR <= deb[iNoeud] and fin[iNoeud] <= finR)
		{
			int iPos = lower_bound(seg[iNoeud].begin(), seg[iNoeud].end(), borne)
				- seg[iNoeud].begin();
			return (seg[iNoeud].size() - iPos)%2;
		}
		return query(2*iNoeud, debR, finR, borne)
			!= query(2*iNoeud+1, debR, finR, borne);
	}
};

// Si Ai = Bi osef
// WLoG : Ai < Bi
// Si Tj >= Bi : swap. Si Tj < Ai : osef, sinon : on a toujours Bi apres
// On peut donc trouver le dernier j tq Ai <= Tj < Bi puis compter le nombre de k > j tq Tk >= Bi

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int nbCartes, nbOperations;
	cin >> nbCartes >> nbOperations;
	vector<pair<int, int>> cartes(nbCartes);
	for (auto &[A, B] : cartes)
		cin >> A >> B;

	vector<int> operations(nbOperations);
	for (auto &v : operations)
		cin >> v;
	sort(cartes.begin(), cartes.end(),
			[](pair<int, int> a, pair<int, int> b)
			{
				return max(a.first, a.second) < max(b.first,  b.second);
				});
	vector<pair<int, int>> potentielsOperations;
	vector<int> ordreOp(nbOperations);
	for (int i(0); i < nbOperations; ++i)
		ordreOp[i] = i;
	sort(ordreOp.begin(), ordreOp.end(),
			[&](int i, int j) { return operations[i] < operations[j]; });

	countGreater seg(operations);
	int curOp(0);
	long long sol(0);
	for (auto [A, B] : cartes)
	{
		if (A == B)
		{
			sol += A;
			continue;
		}
		int grand = max(A, B);
		int petit = min(A, B);
		while (curOp < nbOperations and operations[ordreOp[curOp]] < grand)
		{
			while (!potentielsOperations.empty() and 
					potentielsOperations.back().second < ordreOp[curOp])
				potentielsOperations.pop_back();
			auto aAjouter = make_pair(operations[ordreOp[curOp]], ordreOp[curOp]);
			if (potentielsOperations.empty()
					or potentielsOperations.back().first != aAjouter.first)
				potentielsOperations.emplace_back(aAjouter);
			curOp++;
		}
		int iDeb = -1;
		if (!potentielsOperations.empty() and potentielsOperations.back().first >= petit)
		{
			int iPos = lower_bound(potentielsOperations.begin(), potentielsOperations.end(), make_pair(petit, 0)) - potentielsOperations.begin();
			iDeb = potentielsOperations[iPos].second;
		}
		bool nbInv = seg.query(1, iDeb+1, nbOperations-1, grand);
		int choisie = A;
		if (A > B)
		{
			if (nbInv)
				choisie = B;
		}
		else
		{
			if (iDeb == -1)
			{
				if (nbInv)
					choisie = B;
			}
			else
			{
				if (!nbInv)
					choisie = B;
			}
		}
		sol += choisie;
	}
	cout << sol << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65