Submission #429808

#	Time	Username	Problem	Language	Result	Execution time	Memory
429808		Mounir	Jousting tournament (IOI12_tournament)	C++14	0 / 100	39 ms	2084 KiB

tournament

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

const int N = (1 << 18);
int nDebuts[N * 2];
int cumul[N];

bool onGagne(int fin, int deb){
	int sum = cumul[fin];
	if (deb > 0)
		sum -= cumul[deb - 1];
	return (sum == 0);
}

int getSum(int gauche, int droite){
	if (gauche > droite)
		return 0;
	if (gauche%2 == 1)
		return nDebuts[gauche] + getSum(gauche + 1, droite);
	if (droite%2 == 0)
		return nDebuts[droite] + getSum(gauche, droite - 1);
	return getSum(gauche / 2, droite / 2);
}

struct Noeud {
	int ajout;
	bool estMort;

	void mourir(){
		estMort = true;
	}

	void ajouter(int delta){
		if (!estMort)
			ajout += delta;
	}
};

Noeud arbre[N * 2];
void push(int noeud){
	for (int enfant = noeud * 2; enfant <= noeud * 2 + 1; enfant++){
		arbre[enfant].ajouter(arbre[noeud].ajout);
		if (arbre[noeud].estMort)
			arbre[enfant].mourir();
	}

	arbre[noeud].ajout = 0;
}


void update(int noeud, int curl, int curr, int reql, int reqr, int typeOp){
	if (curl > reqr || reql > curr)
		return;
	if (reql <= curl && curr <= reqr){
		if (typeOp == 0)
			arbre[noeud].mourir();
		else if (typeOp == 1)
			arbre[noeud].ajouter(1);
		return;
	}

	push(noeud);
	int milieu = (curl + curr)/2;
	update(noeud * 2, curl, milieu, reql, reqr, typeOp);
	update(noeud * 2 + 1, milieu + 1, curr, reql, reqr, typeOp);
}

int GetBestPosition(int nGars, int nRounds, int rangPaume, int *rangs, int *gauche, int *droite) {
	for (int iRound = 0; iRound < nRounds; ++iRound){
		int compression  = droite[iRound] - gauche[iRound];
		gauche[iRound] += getSum(N, N + gauche[iRound] - 1);
		droite[iRound] += getSum(N, N + droite[iRound]);
		for (int noeud = N + gauche[iRound]; noeud > 0; noeud /= 2)
			nDebuts[noeud] += compression;
	}
/*
	for (int iRound = 0; iRound < nRounds; ++iRound)
		cout << "inter " << gauche[iRound] << " " << droite[iRound] << endl;
*/
	for (int ind = 0; ind < nGars - 1; ++ind){
		cumul[ind] = (rangs[ind] > rangPaume);
		if (ind != 0)
			cumul[ind] += cumul[ind - 1];
	}

	for (int iRound = 0; iRound < nRounds; ++iRound)
		update(1, 0, N - 1, gauche[iRound], droite[iRound], onGagne(gauche[iRound], droite[iRound]));
	

	int iOpt = -1;
//	cout << "RES ";
	for (int ind = 0; ind < nGars; ++ind){
		update(1, 0, N - 1, ind, ind, 2);
		if (iOpt == -1 || arbre[N + iOpt].ajout < arbre[N + ind].ajout)
			iOpt = ind;
//		cout << arbre[N + ind].ajout << " ";
	}
//	cout << endl;
	return iOpt;
}

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