#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
// <|°_°|>
const int INFINI = (1000 * 1000 * 1000);
const int MAX_CHEVALIERS = (100 * 1000);
const int LOG = (16);
int NbVictoires[MAX_CHEVALIERS];
int Fenwick[MAX_CHEVALIERS];
void Add(int id, int val) {
for (int i = id; i < MAX_CHEVALIERS; i |= (i + 1))
{
Fenwick[i] += val;
}
return;
}
int FindFirst(int nb) {
int ans = -1;
int sum = 0;
for (int i = (1 << LOG); i > 0; i >>= 1)
{
if (ans + i < MAX_CHEVALIERS && sum + Fenwick[ans + i] < nb)
{
ans += i;
sum += Fenwick[ans];
}
}
return ans + 1;
}
int GetBestPosition(int nbChevaliers, int nbRounds, int nouvRang, int *Rang, int *Left, int *Right) {
for (int i = 0; i < nbChevaliers; i ++)
{
NbVictoires[i] = 0;
Add(i, 1);
}
int ans = 0;
for (int i = 0; i < nbRounds; i ++)
{
Left[i] ++, Right[i] ++;
int maxRang = -1, maxDP = - INFINI;
vector <int> pos;
for (int j = Left[i]; j < Right[i]; j ++)
{
pos.push_back(FindFirst(j));
}
int last = FindFirst(Right[i]);
for (int a : pos)
{
maxRang = max(maxRang, Rang[a]);
maxDP = max(maxDP, NbVictoires[a]);
}
maxDP = max(maxDP, NbVictoires[last]);
maxDP ++;
if (maxRang > nouvRang)
maxDP = - INFINI;
maxRang = max(maxRang, Rang[last]);
for (int a : pos)
{
Add(a, -1);
NbVictoires[a] = - INFINI;
}
Rang[last] = maxRang;
NbVictoires[last] = maxDP;
ans = max(ans, maxDP);
}
return ans;
}
