제출 #946076

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
946076		Sandarach151	마상시합 토너먼트 (IOI12_tournament)	C++17	0 / 100	38 ms	4880 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;
	}
};

struct segtree{
	int n;
	vector<pair<int, int> > arr;
	vector<int> tree;
	vector<bool> flag;
	
	segtree(int _n): n(_n){
		arr.resize(n);
		tree.resize(4*n);
		flag.assign(4*n, false);
		build(0, 0, n-1);
	}
	
	void propogate(int ncur, int nleft, int nright){
		if(nleft!=nright && flag[ncur]==true){
			flag[2*ncur+1]=true;
			flag[2*ncur+2]=true;
			tree[2*ncur+1]=0;
			tree[2*ncur+2]=0;
		}
	}
	
	void build(int ncur, int nleft, int nright){
		if(nleft==nright){
			tree[ncur] = 1;
			arr[nleft] = {nleft, nleft};
		}
		else{
			int nmid = (nleft+nright)/2;
			build(2*ncur+1, nleft, nmid);
			build(2*ncur+2, nmid+1, nright);
			tree[ncur] = tree[2*ncur+1] + tree[2*ncur+2];
		}
	}
	
	int getSum(int qleft, int qright, int ncur, int nleft, int nright){
		if(qleft>nright || qright<nleft || flag[ncur]){
			return 0;
		}
		else if(qleft<=nleft && nright<=qright){
			return tree[ncur];
		}
		else{
			int nmid = (nleft+nright)/2;
			return getSum(qleft, qright, 2*ncur+1, nleft, nmid) + getSum(qleft, qright, 2*ncur+2, nmid+1, nright);
		}
	}
	
	void update(int qleft, int qright, int ncur, int nleft, int nright){
		if(qleft>nright || qright<nleft || flag[ncur]){
			return;
		}
		else if(qleft<=nleft && nright<=qright){
			flag[ncur] = true;
			tree[ncur] = 0;
		}
		else{
			int nmid = (nleft+nright)/2;
			update(qleft, qright, 2*ncur+1, nleft, nmid);
			update(qleft, qright, 2*ncur+2, nmid+1, nright);
			tree[ncur]=tree[2*ncur+1]+tree[2*ncur+2];
		}
	}
	
	int findpos(int pos, int past, int ncur, int nleft, int nright){
		if(nleft==nright){
			return nleft;
		}
		else{
			propogate(ncur, nleft, nright);
			int nmid = (nleft+nright)/2;
			if(past+tree[2*ncur+1]>=pos){
				return findpos(pos, past, 2*ncur+1, nleft, nmid);
			}
			else{
				return findpos(pos, past+tree[2*ncur+1], 2*ncur+2, nmid+1, nright);
			}
		}
	}
	
	pair<int, int> query(int left, int right){
		int curleft = findpos(left, 0, 0, 0, n-1);
		int curright = findpos(right, 0, 0, 0, n-1);
		update(curleft+1, curright, 0, 0, n-1);
		arr[curleft].second = arr[curright].second;
		return {arr[curleft].first, arr[curleft].second};
	}
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	segtree poss(N);
	vector<int> ss;
	vector<int> ee;
	for(int i=0; i<C; i++){
		pair<int, int> temp = poss.query(S[i]+1, E[i]+1);
		ss.push_back(temp.first);
		ee.push_back(temp.second);
	}
	/*
	for(int i=0; i<C; i++){
		cout << ss[i] << ' ';
	}
	cout << '\n';
	for(int i=0; i<C; i++){
		cout << ee[i] << ' ';
	}
	cout << '\n';
	*/
	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(ss[i], ee[i]-1, 0, 0, N)<R){
			range.update(ss[i], ee[i]);
		}
	}
	return range.getAns();
}

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