Submission #913024

#	Time	Username	Problem	Language	Result	Execution time	Memory
913024		Faisal_Saqib	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1052 ms	1624 KiB

tournament

#pragma once
#include <iostream>
using namespace std;
const int NPA=5201;
int cs[NPA],ce[NPA],a[NPA],mi[NPA],mx[NPA];
struct SegmentTree
{
	int mx=0;
	int s,e;
	SegmentTree* next[2];
	SegmentTree(int l,int r)
	{
		s=l;
		e=r;
		if(s!=e)
		{
			int mid=(s+e)/2;
			next[0]=new SegmentTree(s,mid);
			next[1]=new SegmentTree(mid+1,e);
		}
	}
	void Update(int l,int val)
	{
		if(e<l or l<s)
			return;
		if(s==e)
		{
			mx=val;
			return;
		}
		next[0]->Update(l,val);
		next[1]->Update(l,val);
		mx=max(next[0]->mx,next[1]->mx);
	}
	int get(int l,int r)
	{
		if(e<l or r<s)
			return 0;
		if(l<=s and e<=r)
			return mx;
		return max(next[0]->get(l,r),next[1]->get(l,r));
	}
};
int GetBestPosition(int n, int c, int r, int k[], int s[], int e[])
{
	// Lets change the queries from the changed array to the original array
	for(int i=0;i<n;i++)
		a[i]=mi[i]=mx[i]=i;
	int len=n;
	for(int ro=0;ro<c;ro++)
	{
		int ns=a[s[ro]];
		int ne=a[e[ro]];
		for(int l=s[ro];l<=e[ro];l++)
		{
			ns=min(ns,mi[a[l]]);
			ne=max(ne,mx[a[l]]);
		}
		for(int l=s[ro];l<=e[ro];l++)
		{
			mi[a[l]]=min(ns,mi[a[l]]);
			mx[a[l]]=max(ne,mx[a[l]]);
		}
		for(int j=e[ro];j<len;j++)
			a[j+s[ro]-e[ro]]=a[j];
		len=len-e[ro]+s[ro];
		cs[ro]=ns;
		ce[ro]=ne;
	}
	int wins=0;
	int poss=0;
	SegmentTree* st=new SegmentTree(0,n-1);
	for(int p=0;p<(n-1);p++)
	{
		int win=0;
		for(int j=0;j<p;j++)
			a[j]=k[j];
		a[p]=r;
		for(int j=p;j<(n-1);j++)
			a[j+1]=k[j];
		for(int lk=0;lk<n;lk++)
			st->Update(lk,a[lk]);
		for(int round=0;round<c;round++)
		{
			int mx=st->get(cs[round],ce[round]);
			if(mx==r)
				win++;
		}
		if(wins<win)
		{
			wins=win;
			poss=p;
		}
	}
	return poss;
}

Compilation message (stderr)

tournament.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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