제출 #429977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
429977		Mounir	마상시합 토너먼트 (IOI12_tournament)	C++14	0 / 100	84 ms	13416 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;
	}
};

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

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

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 curl, int curr, int reql, int reqr, int a, int b){
	if (curr <= reql || reqr <= curl)
		return -OO;
	if (reql <= curl && curr <= reqr){
		arbre[noeud].affine(a, b);
		return arbre[noeud].maxi;
	}

	push(noeud);
	int milieu = (curl + curr)/2;
	int maxl = getMax(noeud * 2, curl, milieu, reql, reqr, a, b), maxr = getMax(noeud * 2 + 1, milieu + 1, curr, 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, 0, N - 1, ng, ng + 1, 1, 0);
		getMax(1, 0, N - 1, ng, nd, 0, pref);
		getMax(1, 0, N - 1, nd, N, 1, -(droite[iRound] - gauche[iRound]));

		gauche[iRound] = ng;
		droite[iRound] = nd;
	//	cout << "t" << 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){
		if (onGagne(gauche[iRound] + 1, droite[iRound])){
			res[gauche[iRound]]++;
			res[droite[iRound]]--;
		}
	}
	

	int iOpt = 0;
	//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;
}

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