Submission #1017787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017787		NintsiChkhaidze	Jousting tournament (IOI12_tournament)	C++17	17 / 100	1060 ms	2776 KiB

tournament

#include <bits/stdc++.h>
#define pb push_back
#define pii pair <int,int>
#define f first
#define s second
#define left h*2,l,(l+r)/2
#define right h*2+1,(l+r)/2+1,r
using namespace std;
const int M = 5000+5;
int arr[M];
bool lz[4*M];
pair<pii,int> t[4*M];

void build(int h,int l,int r){
	lz[h] = 0;
	if (l == r){
		t[h] = {{arr[l],l},1};
		return;
	}
	
	build(left);
	build(right);
	t[h].s=t[h*2].s+t[h*2+1].s;
	t[h].f=max(t[h*2].f,t[h*2+1].f);
}

void push(int h){
	if(!lz[h]) return ;
	lz[h*2] |= lz[h];
	lz[h*2+1] |= lz[h];
	t[h*2] = t[h*2+1] = {{0,0},0};
	lz[h]=0;
}

void updrange(int h,int l,int r,int L,int R){
	if (r < L || R < l) return;
	if (L <= l && r <= R) {
		t[h] = {{0,0},0};
		lz[h] = 1;
		return;
	}	
	push(h);
	updrange(left,L,R);
	updrange(right,L,R);
	t[h].s=t[h*2].s+t[h*2+1].s;
	t[h].f=max(t[h*2].f,t[h*2+1].f);
}

void upd(int h,int l,int r,int idx){
	if (l == r){
		t[h] = {{arr[l],l},1};
		return;
	}
	push(h);
	if(idx>(l+r)/2) upd(right,idx);
	else upd(left,idx);
	t[h].s=t[h*2].s+t[h*2+1].s;
	t[h].f=max(t[h*2].f,t[h*2+1].f);
}

int get(int h,int l,int r,int k){
	if (l == r) return l;
	push(h);
	if (t[h*2].s >= k) return get(left,k);
	return get(right,k-t[h*2].s);
}

pii getmax(int h,int l,int r,int L,int R){
	if (r < L || R < l) return {0,0};
	if (L <= l && r <= R) return t[h].f;
	push(h);
	return max(getmax(left,L,R),getmax(right,L,R));
}

int GetBestPosition(int N, int C, int R, int K[], int S[], int E[]){
	int n = N;
	int ans=-1,pos=-1;
	for (int i=0;i<N;i++){
		vector <int> v;
		int l = 0;
		for (int j = 0; j < N; j++){
			if (i == j) v.pb(R);
			else v.pb(K[l++]);
		}
		
		for (int j = 1; j <= n; j++){
			arr[j] = v[j - 1] + 1;	
		}
		build(1,1,n);
		
		int cur = 0;
		for (int j = 0; j < C; j++){
			int l = S[j] + 1,r = E[j] + 1;
			int l1 = get(1,1,n,l);
			int r1 = get(1,1,n,r);
			
			pii res = getmax(1,1,n,l1,r1);
			if (res.f == R + 1) cur += 1;
			updrange(1,1,n,l1,r1);
			upd(1,1,n,res.s);
		}
		
		if (cur > ans){
			ans = cur;
			pos = i;
		}
	}
	
	return pos;
}

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