Submission #430106

#	Time	Username	Problem	Language	Result	Execution time	Memory
430106		Mounir	Jousting tournament (IOI12_tournament)	C++14	100 / 100	307 ms	14732 KiB

tournament

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

const int N = (1 << 18), OO = 1e9;
struct Noeud {
	int mini, maxi, a, b;
	int deb, fin;

	void affine(int na, int nb){
		a *= na;
		b = b * na + nb;
		mini = mini * na + nb;
		maxi = maxi * na + nb;

		if (mini > maxi)
			swap(mini, maxi);
	}
};

Noeud arbre[N * 2];
int cumul[N], res[N];

void push(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; ++enfant)
		arbre[enfant].affine(arbre[noeud].a, arbre[noeud].b);
	arbre[noeud].a = 1, arbre[noeud].b = 0;
}

int getKth(int noeud, int k){
	if (noeud >= N)
		return noeud - N;
	push(noeud);
	if (arbre[noeud * 2].maxi >= k)
		return getKth(noeud * 2, k);
	return getKth(noeud * 2 + 1, k);
}

int getMax(int noeud,  int reql, int reqr, int a, int b){
	if (arbre[noeud].fin <= reql || reqr <= arbre[noeud].deb)
		return -OO;
	if (reql <= arbre[noeud].deb && arbre[noeud].fin <= reqr){
		arbre[noeud].affine(a, b);
		return arbre[noeud].maxi;
	}

	push(noeud);
	int maxl = getMax(noeud * 2,  reql, reqr, a, b), maxr = getMax(noeud * 2 + 1, reql, reqr, a, b);
	arbre[noeud].mini = min(arbre[noeud * 2].mini, arbre[noeud * 2 + 1].mini);
	arbre[noeud].maxi = max(arbre[noeud * 2].maxi, arbre[noeud * 2 + 1].maxi);
	return max(maxl, maxr);
}

int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
	for (int ind = N; ind < 2 * N; ++ind)
		arbre[ind] = {ind - N, ind - N, 1, 0, ind - N, ind - N + 1};
	for (int ind = N - 1; ind > 0; --ind)
		arbre[ind] = {arbre[ind * 2].mini, arbre[ind * 2 + 1].maxi, 1, 0, arbre[ind * 2].deb, arbre[ind * 2 + 1].fin};

	for (int iRound = 0; iRound < nRounds; ++iRound){
		int ng = getKth(1, gauche[iRound]), nd = getKth(1, droite[iRound] + 1);

		int pref = getMax(1, ng, ng + 1, 1, 0);
		getMax(1, ng, nd, 0, pref);
		getMax(1, nd, N, 1, -(droite[iRound] - gauche[iRound]));

		gauche[iRound] = ng;
		droite[iRound] = nd;
	//	cout << "t" << gauche[iRound] << " " << droite[iRound] << endl;
	}

	cumul[0] = 0;
	//cout << "cum";
	for (int ind = 1; ind < nGars; ++ind){
		cumul[ind] = (rangs[ind - 1] > rangPaume) + cumul[ind - 1];
	//	cout << cumul[ind] << " ";
	}
	//cout << endl;

	for (int iRound = 0; iRound < nRounds; ++iRound){
		gauche[iRound]++;
	//	cout << "a " << gauche[iRound]  << " " << droite[iRound] +1  << endl;
		if ((cumul[droite[iRound] - 1] - cumul[gauche[iRound] - 1]) == 0){
			//cout << "a " << gauche[iRound]  << " " << droite[iRound] +1  << endl;
			res[gauche[iRound]]++;
			res[droite[iRound] + 1]--;
		}
	}
	

	int iOpt = 1;
//	cout << "res " << res[0] << " ";
	for (int ind = 1; ind <= nGars; ++ind){
		res[ind] += res[ind - 1];
	//	cout << res[ind] << " ";
		if (res[ind] > res[iOpt])
			iOpt = ind;
	}
	//cout << endl;
	return iOpt - 1;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51