Submission #400758

#	Time	Username	Problem	Language	Result	Execution time	Memory
400758		EncryptingWolf	Jousting tournament (IOI12_tournament)	C++14	0 / 100	23 ms	3532 KiB

tournament

#include <vector>
#include <deque>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
using namespace std;
//typedef long long int;
#define FOR(i,x,y) for (int i = x; i<y; i++)

int sumS[262144];
int sum2S[262144];

int maxS[262144];

//int nums[262144];

int sumSegment(int a, int b)
{
	a+= 131072; b+= 131072;
	int sum = 0;
	while (a <= b)
	{
		if ((a % 2)) sum += sumS[a++];
		if (!(b % 2)) sum += sumS[b--];
		a /= 2; b /= 2;
	}
	return sum;
}
void updateSumSegment(int a, int p)
{
	a+= 131072;
	while (a>0)
	{
		sumS[a] += p;
		a /= 2;
	}
}

int sum2Segment(int a, int b)
{
	a += 131072; b += 131072;
	int sum = 0;
	while (a <= b)
	{
		if ((a % 2)) sum += sum2S[a++];
		if (!(b % 2)) sum += sum2S[b--];
		a /= 2; b /= 2;
	}
	return sum;
}
void update2SumSegment(int a, int p)
{
	a += 131072;
	while (a > 0)
	{
		sum2S[a] += p;
		a /= 2;
	}
}

int maxSegment(int a, int b)
{
	a+= 131072; b+= 131072;
	int m = -1;
	while (a <= b)
	{
		if ((a % 2)) m = max(m, maxS[a++]);
		if (!(b % 2)) m = max(m, maxS[b--]);
		a /= 2; b /= 2;
	}
	return m;
}
void updateMaxSegment(int a, int p)
{
	a+= 131072;
	while (a > 0)
	{
		maxS[a] = max(maxS[a],p);
		a /= 2;
	}
}

int n, c, r;
int s[262144];
int e[262144];
int k[262144];
int sn[262144];
int en[262144];

int prefixThing[262144];

int GetBestPosition(int N, int C, int R,  int *K, int *S, int *E)
{
	n = N;
	c = C;
	r = R;
	updateSumSegment(0, 0);
	update2SumSegment(0, 0);

	FOR(i, 1, n)
	{
		updateSumSegment(i, 1);
		update2SumSegment(i, 1);
	}
	FOR(i, 0, c)
	{
		s[i] = S[i];
		e[i] = E[i];
	}
	FOR(i, 0, n - 1)
	{
		k[i] = K[i];
		updateMaxSegment(i, k[i]);
	}

	FOR(i, 0, c)
	{
		sn[i] = sumSegment(0, s[i]);
		en[i] = sum2Segment(0, e[i]);
		updateSumSegment(s[i]+1, e[i] - s[i]);
		update2SumSegment(s[i], e[i] - s[i]);
	}

	FOR(i, 0, c)
	{
			if (r > maxSegment(sn[i], en[i]-1))
		{
			prefixThing[sn[i]] += 1;
			prefixThing[en[i]+1] -= 1;
		}
	}
	
	int total = 0;
	int best = 0;
	int bestIndex = 0;
	FOR(i, 0, n)
	{
		total += prefixThing[i];
		if (total > best)
		{
			bestIndex = i;
			best = total;
		}
	}
	cout << bestIndex;
	return bestIndex;
}

/*int main()
{
	//int nR, cR, rR;
	//cout << "Test" << endl;

	//int sR[262144];
	//int eR[262144];
	//int kR[262144];
	//cout << "Test" << endl;
	cin >> n >> c >> r;

	FOR(i, 0, n-1)
	{
		cin >> k[i];
	}

	FOR(i, 0, c)
	{
		cin >> s[i];
		cin >> e[i];
	}
	GetBestPosition(n, c, r, k, s, e);
	return 0;
}*/

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