oj.uz

답안 #430106

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
430106 2021-06-16T11:30:34 Z Mounir 마상시합 토너먼트 (IOI12_tournament) C++14
100 / 100
 307 ms 14732 KB 
#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.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12576 KB Output is correct
2 Correct 11 ms 12620 KB Output is correct
3 Correct 10 ms 12492 KB Output is correct
4 Correct 10 ms 12620 KB Output is correct
5 Correct 9 ms 12512 KB Output is correct
6 Correct 11 ms 12592 KB Output is correct
7 Correct 10 ms 12512 KB Output is correct
8 Correct 10 ms 12492 KB Output is correct
9 Correct 9 ms 12620 KB Output is correct
10 Correct 9 ms 12620 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12548 KB Output is correct
2 Correct 31 ms 12608 KB Output is correct
3 Correct 15 ms 12592 KB Output is correct
4 Correct 22 ms 12656 KB Output is correct
5 Correct 20 ms 12564 KB Output is correct
6 Correct 16 ms 12648 KB Output is correct
7 Correct 26 ms 12620 KB Output is correct
8 Correct 29 ms 12664 KB Output is correct
9 Correct 12 ms 12620 KB Output is correct
10 Correct 32 ms 12756 KB Output is correct

Subtask #3
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 13428 KB Output is correct
2 Correct 269 ms 14732 KB Output is correct
3 Correct 39 ms 13984 KB Output is correct
4 Correct 259 ms 14532 KB Output is correct
5 Correct 266 ms 14352 KB Output is correct
6 Correct 189 ms 14248 KB Output is correct
7 Correct 307 ms 14512 KB Output is correct
8 Correct 258 ms 14512 KB Output is correct
9 Correct 21 ms 13772 KB Output is correct
10 Correct 47 ms 14372 KB Output is correct