Submission #576520

#	Time	Username	Problem	Language	Result	Execution time	Memory
576520		benson1029	Jousting tournament (IOI12_tournament)	C++14	100 / 100	142 ms	7224 KiB

tournament

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

int seg[400005];
int v[400005];
int tmp[400005];
int l[100005], r[100005];
int seg2[400005];
int k[100005];

void seg_set(int x, int l, int r, int p, int v) {
	if(l==r) {
		seg[x] = v;
	} else {
		if(p<=(l+r)/2) seg_set(x*2, l, (l+r)/2, p, v);
		else seg_set(x*2+1, (l+r)/2+1, r, p, v);
		seg[x] = seg[x*2] + seg[x*2+1];
	}
}

int seg_qry(int x, int l, int r, int v) {
	if(l==r) return l;
	else {
		if(v <= seg[x*2]) return seg_qry(x*2, l, (l+r)/2, v);
		else return seg_qry(x*2+1, (l+r)/2+1, r, v-seg[x*2]);
	}
}

void seg2_build(int x, int l, int r) {
	if(l==r) seg2[x] = k[l];
	else {
		seg2_build(x*2, l, (l+r)/2);
		seg2_build(x*2+1, (l+r)/2+1, r);
		seg2[x] = max(seg2[x*2], seg2[x*2+1]);
	}
}

int seg2_qry(int x, int l, int r, int ll, int rr) {
	if(l > rr || r < ll) return -1e9;
	if(ll <= l && r <= rr) return seg2[x];
	return max(seg2_qry(x*2, l, (l+r)/2, ll, rr), seg2_qry(x*2+1, (l+r)/2+1, r, ll, rr));
}

int diff[100005];

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i=0; i<N; i++) seg_set(1, 0, N-1, i, 1);
	for(int i=0; i<C; i++) {
		S[i]++; E[i]++;
		for(int j=S[i]; j<=E[i]; j++) {
			tmp[j] = seg_qry(1, 0, N-1, j);
		}
		l[i] = tmp[S[i]];
		r[i] = tmp[E[i]] + v[tmp[E[i]]];
		for(int j=S[i]+1; j<=E[i]; j++) {
			v[tmp[S[i]]] += v[tmp[j]];
			seg_set(1, 0, N-1, tmp[j], 0);
		}
		v[tmp[S[i]]] += (E[i] - S[i]);
	}
	for(int i=0; i<N-1; i++) k[i] = K[i];
	seg2_build(1, 0, N-2);
	for(int i=0; i<C; i++) {
		if(R > seg2_qry(1, 0, N-2, l[i], r[i]-1)) {
			diff[l[i]]++;
			diff[r[i]+1]--;
		}
	}
	int ans = -1, pos = -1;
	for(int i=0; i<N; i++) {
		if(i) diff[i] += diff[i-1];
		if(diff[i] > ans) {
			ans = diff[i];
			pos = i;
		}
	}
	return pos;
}

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