Submission #73831

#	Time	Username	Problem	Language	Result	Execution time	Memory
73831		FLDutchman	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1069 ms	4916 KiB

tournament

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

typedef int INT;

#define pb push_back
#define fst first
#define snd second
#define FOR(i,l,r) for(int i = (l); i < (r); i++)

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

void prop(int,int,int);

vi tsum, tmax, lazy;
vi arr;

void upds(int n){
	tsum[n] = tsum[n<<1] + tsum[n<<1|1];
}

void buildsum(int lb, int rb, int n){
	if(lb+1==rb) {
		tsum[n] = 1;
		return;
	}
	int mb = (lb+rb)/2;
	buildsum(lb,mb,n<<1);
	buildsum(mb,rb,n<<1|1);
	upds(n);
}

void add(int l, int r, int lb, int rb, int n){
	//cerr<<l<<" "<<r<<" "<<lb<<" "<<rb<<" "<<n<<endl;
	if(l <= lb and rb <= r) {
		lazy[n] = 1;
		tsum[n] = 0;
		return;
	}
	if(lazy[n]) prop(lb,rb,n);
	int mb = (lb+rb)/2;
	if(l < mb) add(l,r,lb,mb,n<<1);
	if(r > mb) add(l,r,mb,rb,n<<1|1);
	upds(n);
}

void prop(int lb, int rb, int n){
	int mb = (lb+rb)/2;
	add(lb,rb,lb,mb,n<<1);
	add(lb,rb,mb,rb,n<<1|1);
	lazy[n] = 0;
}

int getidx(int i, int lb, int rb, int n){
	if(lb + 1 == rb) return lb;
	if(lazy[n]) prop(lb,rb,n);
	if(i == tsum[n]) return rb;
	int mb = (lb+rb)/2;
	if(i < tsum[n<<1]) return getidx(i, lb, mb, n<<1);
	return getidx(i-tsum[n<<1], mb,rb,n<<1|1);
}


vii intervals;

vii idx;

INT GetBestPosition(INT N, INT C, INT R, INT *K, INT *S, INT *E) {
	idx.resize(N);
	lazy.assign(4*N,0);
	tsum.assign(4*N,0);
	tmax.assign(4*N,0);
	buildsum(0, N, 1);

	FOR(i,0,N) arr.pb(K[i]);
	FOR(i, 0, N) idx[i] = {i,i};
	FOR(i, 0, C){
		int l = getidx(S[i], 0,N,1), r = getidx(E[i]+1, 0, N, 1) - 1;
		intervals.pb({l,r});
		add(l+1,r+1,0,N,1);
		//cout<<tsum[1]<<endl;
	}
	//for(ii p : intervals) cout << p.fst << " " << p.snd << endl;
	vi val(C, -1);
	FOR(i, 0, C) FOR(j, intervals[i].fst, intervals[i].snd){
		val[i] = max(val[i], K[j]);
	}
	ii best = {-1, -1e9};
	//for(int k : val) cout << k << endl;
	FOR(i, 0, N) {
		int tot = 0;
		FOR(c,0,C) if(intervals[c].fst <= i and i <= intervals[c].snd){
			tot += val[c] < R;	
		}	
		best = max(best, {tot,-i});
	}
	return -best.snd;
}

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