| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1253443 | lumine88 | Jousting tournament (IOI12_tournament) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
#define yoimiya int
const yoimiya nmax=1e5+163,inf=1e9,mod=1e9+7,MAX=4000000;
yoimiya n,m,late,rnk[nmax],idx[nmax],leaf;
vector<yoimiya> tree[nmax];
yoimiya dfs(yoimiya u)
{
if (u==0)
{
leaf++;
return -1;
}
yoimiya start=leaf,res=-1;
for (yoimiya v:tree[u])
{
res=max(res,dfs(v));
if (v!=tree[u].back())
res=max(res,rnk[leaf]);
}
if (res<late)
{
idx[start]++;
idx[leaf]--;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen("yoimiya.INP","r",stdin);
//freopen("yoimiya.OUT","w",stdout);
cin>>n>>m>>late;
for (int i=1;i<n;i++)
cin>>rnk[i];
for (int i=1,l,r;i<=m;i++)
{
cin>>l>>r;
for (int j=l;j<=r;j++)
{
tree[i].push_back(idx[j]);
idx[j]=0;
}
idx[l]=i;
}
memset(idx,0,sizeof idx);
dfs(m);
leaf=0;
for (int i=0;i<n;i++)
{
idx[i+1]+=idx[i];
if (idx[leaf]<idx[i])
leaf=i;
}
cout<<leaf;
}