Submission #132920

#	Time	Username	Problem	Language	Result	Execution time	Memory
132920		arthurconmy	Jousting tournament (IOI12_tournament)	C++14	49 / 100	1077 ms	2896 KiB

tournament

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

const int p2 = 131072;
int st[p2+p2+1];

int query(int l, int r)
{
	l+=p2;
	r+=p2;

	int ans=0;

	while(l<=r)
	{
		if(l%2 == 1) ans=max(ans,st[l++]);
		if(r%2 == 0) ans=max(ans,st[r--]);

		l/=2;
		r/=2;
	}

	return ans;
}

int GetBestPosition(int n, int c, int r, int *K, int *S, int *E)
{
	vector<pair<int,int>> blobs;

	for(int i=0; i<n; i++)
	{
		blobs.push_back({i,i});
	}

	vector<pair<int,int>> I;

	for(int i=0; i<c; i++)
	{
		I.push_back({blobs[S[i]].first,blobs[E[i]].second});
		blobs[S[i]]={blobs[S[i]].first,blobs[E[i]].second};

		if(S[i]==E[i]) continue;

		blobs.erase(blobs.begin()+S[i]+1,blobs.begin()+E[i]+1);
	}

	// for(auto i:I)
	// {
	// 	cout << i.first << " " << i.second << endl; 
	// }

	for(int i=0; i<n-1; i++)
	{
		st[i+p2]=K[i];
	}	

	for(int i=p2-1; i>=1; i--)
	{
		st[i]=max(st[i+i],st[i+i+1]);
	}

	deque<pair<int,int>> good_segs;

	for(auto i:I)
	{
		if(query(i.first,i.second-1) < r) good_segs.push_back(i);
	}

	sort(good_segs.begin(),good_segs.end());

	int best_pos=0;
	int best_lap=0;

	priority_queue<int> cur_segs;

	for(int i=0; i<n; i++)
	{
		while(!cur_segs.empty() && -cur_segs.top()<i) cur_segs.pop();
		while(!good_segs.empty() && good_segs.front().first == i)
		{
			cur_segs.push(-good_segs.front().second);
			good_segs.pop_front();
		}

		if(best_lap < cur_segs.size())
		{
			best_lap = cur_segs.size();
			best_pos=i;
		}
	}

	// cout << best_pos << " " << best_lap << endl;

	return best_pos;
}

#ifdef ARTHUR_LOCAL
	
	int main()
	{
		 // cout << int(pow(2,18)) << endl;

		int K[4];
		int S[3];
		int E[3];

		K[0]=1;
		K[1]=0;
		K[2]=2;
		K[3]=4;

		S[0]=1;
		E[0]=3;

		S[1]=0;
		E[1]=1;

		S[2]=0;
		E[2]=1;

		cout << GetBestPosition(5,3,3,K,S,E);
	}

#endif

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(best_lap < cur_segs.size())
      ~~~~~~~~~^~~~~~~~~~~~~~~~~

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