Submission #348401

#	Time	Username	Problem	Language	Result	Execution time	Memory
348401		dennisstar	Jousting tournament (IOI12_tournament)	C++17	100 / 100	112 ms	6764 KiB

tournament

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


const int MX = 1e5 + 5, SMX = 1<<18;

int N, C, R;
int K[MX], S[MX], E[MX], A[MX];

struct {
	int st[SMX];
	void init(int i, int s, int e) {
		if (s==e) { st[i]=1; return ; }
		int m=(s+e)/2;
		init(i*2, s, m);
		init(i*2+1, m+1, e);
		st[i]=st[i*2]+st[i*2+1];
	}
	int find(int i, int s, int e, int t) {
		if (st[i]<t) return e+1;
		if (s==e) return s;
		int m=(s+e)/2;
		if (st[i*2]>=t) return find(i*2, s, m, t);
		else return find(i*2+1, m+1, e, t-st[i*2]);
	}
	void upd(int i, int s, int e, int l, int r) {
		if (e<l||r<s||!st[i]) return ;
		if (l<=s&&e<=r) { st[i]=0; return ; }
		int m=(s+e)/2;
		upd(i*2, s, m, l, r);
		upd(i*2+1, m+1, e, l, r);
		st[i]=st[i*2]+st[i*2+1];
	}
}S1;

struct {
	int st[SMX];
	void init(int i, int s, int e) {
		if (s==e) { st[i]=K[s]; return ; }
		int m=(s+e)/2;
		init(i*2, s, m);
		init(i*2+1, m+1, e);
		st[i]=max(st[i*2], st[i*2+1]);
	}
	int get(int i, int s, int e, int l, int r) {
		if (e<l||r<s) return 0;
		if (l<=s&&e<=r) return st[i];
		int m=(s+e)/2;
		return max(get(i*2, s, m, l, r), get(i*2+1, m+1, e, l, r));
	}
}S2;

int sol() {
	S1.init(1, 1, N);
	S2.init(1, 1, N-1);

	for (int i=1; i<=C; i++) {
		int l=S1.find(1, 1, N, S[i]), r=S1.find(1, 1, N, E[i]+1)-1;
		S1.upd(1, 1, N, l+1, r);
		if (S2.get(1, 1, N-1, l, r-1)<R) A[l]++, A[r+1]--;
	}

	int mx=0, r=1;
	for (int i=1; i<=N; i++) {
		A[i]+=A[i-1];
		if (A[i]>mx) mx=A[i], r=i;
	}
	return r-1;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	::N=N, ::C=C, ::R=R+1;
	for (int i=1; i<=N-1; i++) ::K[i]=K[i-1]+1;
	for (int i=1; i<=C; i++) ::S[i]=S[i-1]+1, ::E[i]=E[i-1]+1;
	return sol();
}

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