Submission #88409

#	Time	Username	Problem	Language	Result	Execution time	Memory
88409		Pajaraja	Jousting tournament (IOI12_tournament)	C++17	0 / 100	45 ms	4392 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
int seg[2][400028],bag[2][400028],segmax[400028],k[100007],s[100007],e[100007],p[100007],q[100007];
void relax(int ind,int k)
{
	bag[k][2*ind]+=bag[k][ind];
	bag[k][2*ind+1]+=bag[k][ind];
	bag[k][ind]=0;
}
void upd(int l,int r,int lt,int rt,int val,int k,int ind)
{
	if(l>=lt && r<=rt)
	{
		bag[k][ind]+=val;
		return;
	}
	if(r<lt || l>rt) return;
	int s=(l+r)/2;
	upd(l,s,lt,rt,val,k,2*ind);
	upd(s+1,r,lt,rt,val,k,2*ind+1);
}
int val(int l,int r,int poz,int k,int ind)
{
	if(l==r) return bag[k][ind];
	relax(ind,k);
	int s=(l+r)/2;
	if(poz<=s) return val(l,s,poz,k,2*ind);
	return val(s+1,r,poz,k,2*ind+1);
}
int find(int l,int r,int lt,int rt,int ind)
{
	if(l>=lt && r<=rt) return segmax[ind];
	if(r<lt || l>rt) return -1;
	int s=(l+r)/2;
	return fmax(find(l,s,lt,rt,2*ind),find(s+1,r,lt,rt,2*ind+1));
}
void make(int l,int r,int ind)
{
	if(l==r)
	{
		segmax[ind]=k[l];
		return;
	}
	int s=(l+r)/2;
	make(l,s,2*ind);
	make(s+1,r,2*ind+1);
	segmax[ind]=fmax(segmax[2*ind],segmax[2*ind+1]);
}
int GetBestPosition(int N,int C,int R,int K[] ,int S[],int E[])
{
	int n=N,c=C,r=R;
	for(int i=0;i<n-1;i++) k[i]=K[i];
	for(int i=0;i<c;i++) s[i]=S[i];
	for(int i=0;i<c;i++) e[i]=E[i];
	make(0,n-2,1);
	for(int i=0;i<c;i++)
	{
		int a=s[i]+val(0,n,s[i],0,1),b=e[i]+val(0,n,e[i],1,1);
		upd(0,n,a+1,n,e[i]-s[i],0,1);
		upd(0,n,a,n,e[i]-s[i],1,1);
		s[i]=a;
		e[i]=b;
	}
	for(int i=0;i<c;i++) if(find(0,n-2,s[i],e[i]-1,1)<r)
	{
		p[s[i]]++;
		q[e[i]]++;
	}
	int cur=0,max=0,maxind=0;
	for(int i=0;i<n;i++)
	{
		cur+=p[i];
		if(cur>max)
		{
			max=cur;
			maxind=i;
		}
		cur-=q[i];
	}
	return maxind;
}

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