oj.uz

Submission #94660

# Submission time Handle Problem Language Result Execution time Memory
94660 2019-01-22T07:58:12 Z Retro3014 Jousting tournament (IOI12_tournament) C++17
100 / 100
 295 ms 11500 KB 
#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_s3(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;
}

int calc_s1(int x){
	int s = 0, e = v.size()+1, m;
	while(s<e){
		m = (s+e)/2+1;
		if(calc_s3(0, m-1) <= x)	s = m;
		else	e = m-1;	
	}
	return s;
}

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;
	}
}

void update3(int x, int y){
	//cout<<1<<endl;
	while(1){
		int t = calc_s3(x, y);
		//cout<<t<<endl;
		if(t==1)	break;
		int s = x, e = y, m;
		while(s<e){
			m = (s+e)/2;
			if(calc_s3(x, m)==t)	e = m;
			else	s = m+1;
		}
		update1(s, -1);
	}
	//cout<<2<<endl;
	return;
}

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<N; i++) update1(i, 1);
	for(int i=0; i<q.size(); i++){
		Q now = q[i];
		now.s = calc_s1(now.s);
		now.e = calc_s1(now.e+1)-1;
		//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);
			}
		}
		update3(now.s, now.e);
	}
	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;
}

Compilation message

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:101:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~
tournament.cpp:108:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<q.size(); i++){
               ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 892 KB Output is correct
3 Correct 6 ms 760 KB Output is correct
4 Correct 10 ms 888 KB Output is correct
5 Correct 10 ms 836 KB Output is correct
6 Correct 8 ms 888 KB Output is correct
7 Correct 10 ms 888 KB Output is correct
8 Correct 10 ms 888 KB Output is correct
9 Correct 6 ms 764 KB Output is correct
10 Correct 11 ms 892 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4872 KB Output is correct
2 Correct 295 ms 11344 KB Output is correct
3 Correct 118 ms 9072 KB Output is correct
4 Correct 272 ms 11372 KB Output is correct
5 Correct 272 ms 11064 KB Output is correct
6 Correct 203 ms 10476 KB Output is correct
7 Correct 281 ms 11500 KB Output is correct
8 Correct 281 ms 11368 KB Output is correct
9 Correct 113 ms 8816 KB Output is correct
10 Correct 95 ms 9072 KB Output is correct