Submission #71474

#	Time	Username	Problem	Language	Result	Execution time	Memory
71474		Abelyan	Jousting tournament (IOI12_tournament)	C++17	0 / 100	66 ms	3424 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

const int N=100006;
struct node{
	int cnt;	
	int maximum,noRight;
	int height;
	int index;
} sg[4*N];

node operator +(const node a,const node b){
	if (a.height==-1) return b;
	if (b.height==-1) return a;
	node c;
	c.cnt=a.cnt+b.cnt;
	c.maximum=max(a.maximum,b.maximum);
	c.noRight=max(a.maximum,b.noRight);
	if (a.height>=b.height){
		c.height=a.height;
		c.index=a.index;
	}
	else{
		c.height=b.height;
		c.index=b.index;
	}
	return c;
}

void build (int v,int tl,int tr,int arr[]){
	if (tl==tr){
		sg[v].cnt=1;
		sg[v].noRight=0;
		sg[v].maximum=arr[tl];
		sg[v].height=1;
		sg[v].index=tl;
		return;
	}
	int tm=(tl+tr)/2;
	build(v+v,tl,tm,arr);
	build(v+v+1,tm+1,tr,arr);
	sg[v]=sg[v+v]+sg[v+v+1];
}

void del(int v,int tl,int tr,int l,int r){
	if (l>r) return;
	if (l==1 && r==sg[v].cnt){
		sg[v].cnt=0;
		sg[v].maximum=sg[v].noRight=0;
		sg[v].height=-1;
		return;
	}
	int border=sg[v+v].cnt,tm=(tl+tr)/2;
	del(v+v,tl,tm,l,min(border,r));
	del(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
	sg[v]=sg[v+v]+sg[v+v+1];
}

void update (int v,int tl,int tr,int ind,node newNode){
	if (sg[v].cnt==1){
		sg[v].maximum=newNode.maximum;
		sg[v].noRight=newNode.noRight;
		sg[v].height=newNode.height;
		sg[v].index=newNode.index;
		return;
	}
	int border=sg[v+v].cnt,tm=(tl+tr)/2;
	if (ind<=border)
		update(v+v,tl,tm,ind,newNode);
	else
		update(v+v+1,tm+1,tr,ind-border,newNode);
	sg[v]=sg[v+v]+sg[v+v+1];
}

node query(int v,int tl,int tr,int l,int r){
	//cout<<sg[v].cnt<<endl;
	if (l>r) return {0,0,0,-1,-1};
	if (l==1 && r==sg[v].cnt){
		//cout<<sg[v].maximum<<" "<<sg[v].noRight<<endl;
		return sg[v];
	}
	int border=sg[v+v].cnt,tm=(tl+tr)/2;
	node left=query(v+v,tl,tm,l,min(border,r));
	node right=query(v+v+1,tm+1,tr,max(border+1,l)-border,r-border);
	//cout<<left.maximum<<" "<<left.noRight<<" "<<left.index<<" "<<right.maximum<<" "<<right.noRight<<" "<<right.index<<endl;
	return left+right;
}

int GetBestPosition(int n, int q, int addVal, int rank[], int start[], int end[]) {
	pair<int,int> finalAns={-1,0};
	if (n==1) return 0;
	for (int i=0;i<n-1;i++){
		rank[i]++;
	}
	rank[n-1]=0;
	//cout<<rank[n-1]<<endl;
	build(1,0,n-1,rank);
	for (int i=0;i<q;i++){
		node ans=query(1,0,n-1,start[i]+1,end[i]+1);
		del(1,0,n-1,start[i]+2,end[i]+1);
		//cout<<ans.maximum<<" "<<ans.noRight<<" "<<ans.height<<" "<<ans.index<<endl<<endl;
		ans.height++;
		if (ans.noRight<=addVal)
			finalAns=max(finalAns,{ans.height,ans.index});
		update(1,0,n-1,start[i]+1,ans);
	}
	return finalAns.second;
}

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