Submission #1126456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126456		thelegendary08	Jousting tournament (IOI12_tournament)	C++17	100 / 100	217 ms	6208 KiB

tournament

#include<bits/stdc++.h>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define pb push_back
#define vi vector<int>
#define ll long long int
using namespace std;
const int mxn = 1e5 + 5;
int tree[mxn * 4];
int n;
void update(int k, int x){
	k += n;
	tree[k] = x;
	for(k/=2;k>=1;k/=2){
		tree[k] = max(tree[k*2], tree[k*2 + 1]);
	}
}
int quer(int l, int r){
	l += n;
	r += n;
	int ret = 0;
	while(l <= r){
		if(l % 2 == 1){
			ret = max(ret, tree[l++]);
		}
		if(r % 2 == 0){
			ret = max(ret, tree[r--]);
		}
		l/=2; r/=2;
	}
	return ret;
}
vi rupq(mxn * 4, 0);
void add(int k, int x){
	k += n + 1;
	rupq[k] += x;
	for(k/=2;k>=1;k/=2){
		rupq[k] = rupq[k * 2] + rupq[k * 2 + 1];
	}
}
int quer2(int l, int r){
	l += n + 1;
	r += n + 1;
	int ret = 0;
	while(l <= r){
		if(l % 2 == 1)ret += rupq[l++];
		if(r % 2 == 0)ret += rupq[r--];
		l/=2;
		r/=2;
	}
	return ret;
}
void rangeadd(int l, int r, int x){
	add(l, x);
	if(r != n){
		add(r + 1, -x);
	}
}
int GetBestPosition(int N, int C, int R, int *w, int *S, int *E) {
	n = N-1;
	vector<pair<int,int>>quers(C);
	vector<int> v(N+1);
	for(int i=0; i<=N; i++){
		v[i] = i;
	}
	for(int i=0; i<C; i++){
		int rs = v[S[i]];
		int re = v[E[i]+1]-1;
		/*cerr << rs << ' ' << re << '\n';
		for(auto j: v){
			cerr << j << ' ';
		}
		cerr << '\n';*/
		quers[i] = {rs,re};
		/*for(int j=S[i]+1; j<=E[i]; j++){
			v.erase(v.begin()+S[i]+1);
		}*/
		v.erase(v.begin()+S[i]+1, v.begin()+E[i]+1);
	}
		f0r(i, N-1){
			update(i, w[i]);
		}
	//if(N <= 5000){
		f0r(i, C){
			int l = quers[i].first;
			int r = quers[i].second - 1;
			
			
			if(quer(l, r) < R){
				//cout<<l<<' '<<r+1<<'\n';
				//cout<<quer(l,r)<<'\n';
				rangeadd(l, r+1, 1);
			}
		}
		int mx = 0;
		int ans = 0;
		vi diffarr;
		f0r(i,N){
			diffarr.pb(rupq[i + N]);
		}
		vi realarr;
		realarr.pb(diffarr[0]);
		for(int i=1;i<N;i++){
			realarr.pb(realarr[i-1] + diffarr[i]);
		}
		f0r(i, N){
			//cout<<quer2(0,i)<<' ';
			if(realarr[i] > mx){
				mx = realarr[i];
				ans = i;
			}
		}
		//cout<<'\n';
		return ans;
	//}
	//else return 0;
	

}

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