Submission #73833

#	Time	Username	Problem	Language	Result	Execution time	Memory
73833		FLDutchman	Jousting tournament (IOI12_tournament)	C++14	100 / 100	134 ms	20404 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);
}

void updm(int n){
	tmax[n] = max(tmax[n<<1], tmax[n<<1|1]);
}

void buildmax(int lb, int rb, int n){
	if(lb+1==rb){
		tmax[n] = arr[lb];
		return;
	}
	int mb = (lb+rb)/2;
	buildmax(lb,mb,n<<1);
	buildmax(mb,rb,n<<1|1);
	updm(n);
}

int rmq(int l, int r, int lb, int rb, int n){
	//cout<<l<<" "<<r<<" " <<lb<<" "<< rb<<" " << n << endl;
	if(l <= lb and rb <= r) return tmax[n];
	int mb = (lb+rb)/2;
	int res = -1;
	if(l < mb) res = max(res, rmq(l,r,lb,mb,n<<1));
	if(r > mb) res = max(res, rmq(l,r,mb,rb,n<<1|1));
	return res;
}

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-1) arr.pb(K[i]);
	buildmax(0,N-1,1);
	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;
	vii q;
	vi val(C, -1);
	//cout<<"rmq "<<rmq(0,4,0,4,1)<<endl;
	FOR(i, 0, C) {
		ii inter = intervals[i];
		val[i] = rmq(intervals[i].fst, intervals[i].snd, 0, N-1, 1);
		if(val[i] < R) {
			q.pb({inter.fst, 1});
			q.pb({inter.snd+1, -1});
		}
	}
	
	sort(q.begin(), q.end());

	ii best = {-1, -1e9};

	//for(int k : val) cout << k << endl;
	int tot = 0, j = 0;;	
	FOR(i, 0, N) {
		for(; j < q.size() and q[j].fst <= i; j++) tot += q[j].snd; 
			//cout<<tot<<endl;
		best = max(best, {tot,-i});
	}
	return -best.snd;
}

Compilation message (stderr)

tournament.cpp: In function 'INT GetBestPosition(INT, INT, INT, INT*, INT*, INT*)':
tournament.cpp:131:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j < q.size() and q[j].fst <= i; j++) tot += q[j].snd; 
         ~~^~~~~~~~~~

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