제출 #94652

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94652		Retro3014	마상시합 토너먼트 (IOI12_tournament)	C++17	0 / 100	38 ms	4852 KiB

tournament

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;
#define MAX_N 100000
struct Q{
	int s, e;
};
vector<int> v;
vector<Q> q;
int r;
set<int> s;
int sum[MAX_N+1];
int seg1[MAX_N*4+1], seg2[MAX_N*4+1];
int two1, two2;
void init1(){
	two1 = 1; while(two1<v.size()+1)	two1*=2;
	for(int i=0; i<two1*2; i++)	seg1[i] = 0;
}
void init2(){
	two2 = 1; while(two2<v.size()+1)	two2*=2;
	for(int i=0; i<two2*2; i++)	seg2[i] = 0;
}
int ans1, ans2;

int calc_s1(int x, int y){
	int ret = 0;
	x+=two1; y+=two1;
	while(x<=y){
		if(x==y)	return ret+seg1[x];
		if(x%2)	ret+=seg1[x++];
		if(!(y%2))	ret+=seg1[y--];
		x/=2; y/=2;
	}return ret;
}

void update1(int x, int y){
	x+=two1;
	while(x>0){
		seg1[x]+=y;
		x/=2;
	}
}

int calc_s2(int x, int y){
	int ret = 0;
	x+=two2; y+=two2;
	while(x<=y){
		if(x==y)	return ret+seg2[x];
		if(x%2)	ret+=seg2[x++];
		if(!(y%2)) ret+=seg2[y--];
		x/=2; y/=2;
	}return ret;
}

void update2(int x, int y){
	x+=two2;
	while(x>0){
		seg2[x]+=y;
		x/=2;
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	ans1 = ans2 = 0;
	v.clear(); q.clear(); s.clear();
	for(int i=0; i<N-1; i++)	v.push_back(K[i]);
	for(int i=0; i<C; i++)	q.push_back({S[i], E[i]});
	r = R;
	for(int i=0; i<N; i++)	s.insert(i);
	for(int i=0; i<v.size(); i++){
		if(i==0)	sum[i] =  (v[i]>r);
		else if(v[i]<r)	sum[i] = sum[i-1];
		else	sum[i] = sum[i-1]+1;
	}
	init1(); init2();
	for(int i=0; i<q.size(); i++){
		Q now = q[i];
		now.s = now.s + calc_s1(0, now.s-1);
		now.e = now.e + calc_s1(0, now.e);
		//cout<<now.s<<" "<<now.e<<endl;
		if(sum[now.e-1]-sum[now.s-1]==0){
			update2(now.s, 1);
			update2(now.e+1, -1);
		}else{
			set<int>::iterator it = s.lower_bound(now.s);
			while(it!=s.end() && *it<=now.e){
				//cout<<*it<<" "<<i<<endl;
				int t = calc_s2(0, *it);
				if(t>ans2 || (t==ans2 && *it<ans1)){
					ans2 = t; ans1 = *it;
				}
				set<int>::iterator it2 = it;
				it++;
				s.erase(it2);
			}
		}
		update1(q[i].s, q[i].e-q[i].s);
	}
	set<int>::iterator it = s.begin();
	while(it!=s.end()){
		int t = calc_s2(0, *it);
		if(t>ans2 || (t==ans2 && *it<ans1)){
			ans2 = t; ans1 = *it;
		}
		it++;
	}
	return ans1;
}

컴파일 시 표준 에러 (stderr) 메시지

tournament.cpp: In function 'void init1()':
tournament.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  two1 = 1; while(two1<v.size()+1) two1*=2;
                  ~~~~^~~~~~~~~~~
tournament.cpp: In function 'void init2()':
tournament.cpp:23:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  two2 = 1; while(two2<v.size()+1) two2*=2;
                  ~~~~^~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
tournament.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<q.size(); i++){
               ~^~~~~~~~~

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