Submission #945742

#	Time	Username	Problem	Language	Result	Execution time	Memory
945742		Sandarach151	Jousting tournament (IOI12_tournament)	C++17	0 / 100	25 ms	3096 KiB

tournament

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

struct minSegtree{
	int n;
	vector<int> arr;
	vector<int> tree;
	
	minSegtree(vector<int> temp){
		int n = temp.size();
		arr = temp;
		tree.assign(4*n, 0);
		build(0, 0, n-1);
	}
	
	void build(int ncur, int nleft, int nright){
		if(nleft==nright){
			tree[ncur] = arr[nleft];
		}
		else{
			int nmid = (nleft+nright)/2;
			build(2*ncur+1, nleft, nmid);
			build(2*ncur+2, nmid+1, nright);
			tree[ncur] = min(tree[2*ncur+1], tree[2*ncur+2]);
		}
	}
	
	int query(int qleft, int qright, int ncur, int nleft, int nright){
		if(qleft>nright || qright<nleft){
			return n+1;
		}
		else if(qleft<=nleft && nright<=qright){
			return tree[ncur];
		}
		else{
			int nmid = (nleft+nright)/2;
			return min(query(qleft, qright, 2*ncur+1, nleft, nmid), query(qleft, qright, 2*ncur+2, nmid+1, nright));
		}
	}
};

struct rangeSegtree{
	int n;
	vector<int> arr;
	vector<int> tree;
	
	rangeSegtree(int _n): n(_n){
		arr.assign(n+1, 0);
		tree.assign(4*n+4, 0);
	}
	
	int privgetsum(int qleft, int qright, int ncur, int nleft, int nright){
		if(qleft>nright || qright<nleft){
			return 0;
		}
		else if(qleft<=nleft && nright<=qright){
			return tree[ncur];
		}
		else{
			int nmid = (nleft+nright)/2;
			return privgetsum(qleft, qright, 2*ncur+1, nleft, nmid) + privgetsum(qleft, qright, 2*ncur+2, nmid+1, nright);
		}
	}
	
	void privupdate(int pos, int val, int ncur, int nleft, int nright){
		if(nleft==nright){
			arr[pos]+=val;
			tree[ncur]+=val;
		}
		else{
			int nmid = (nleft+nright)/2;
			if(pos<=nmid){
				privupdate(pos, val, 2*ncur+1, nleft, nmid);
			}
			else{
				privupdate(pos, val, 2*ncur+2, nmid+1, nright);
			}
			tree[ncur]=tree[2*ncur+1]+tree[2*ncur+2];
		}
	}
	
	void update(int left, int right){
		privupdate(left, 1, 0, 0, n);
		privupdate(right+1, -1, 0, 0, n);
	}
	
	int getAns(){
		int maxx = 0;
		int ans = 0;
		for(int i=0; i<n; i++){
			int temp = privgetsum(0, i, 0, 0, n);
			if(temp>maxx){
				maxx = temp;
				ans = i;
			}
		}
		return ans;
	}
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	vector<int> arr;
	for(int i=0; i<N-1; i++){
		arr.push_back(K[i]);
	}
	minSegtree tree(arr);
	rangeSegtree range(N);
	for(int i=0; i<C; i++){
		if(tree.query(S[i], E[i]-1, 0, 0, N)<R){
			range.update(S[i], E[i]);
		}
	}
	return range.getAns();
}

			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
			
		

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