Submission #71464

#	Time	Username	Problem	Language	Result	Execution time	Memory
71464		Abelyan	Jousting tournament (IOI12_tournament)	C++17	0 / 100	36 ms	6276 KiB

tournament

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

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

node operator +(const node a,const node b){
	node c;
	c.cnt=a.cnt+b.cnt;
	c.maximum=max(a.maximum,b.maximum);
	c.noRight=max(a.maximum,b.noRight);
	c.height=max(a.height,b.height);
	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;
		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=0;
		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;
		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){
	
	if (l>r) return {0,0,0,0};
	//cout<<l<<" "<<r<<" "<<sg[v].cnt<<endl;
	if (l==1 && r==sg[v].cnt){
		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);
	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;
	build(1,0,n-2,rank);
	for (int i=0;i<q;i++){
		node ans=query(1,0,n-2,start[i]+1,end[i]+1);
		del(1,0,n-2,start[i]+2,end[i]+1);
		ans.height++;
		finalAns=max(finalAns,{ans.height,start[i]+1});
		update(1,0,n-2,start[i]+1,ans);
	}
	return finalAns.second;
}

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