oj.uz

답안 #400758

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400758 2021-05-08T15:53:41 Z EncryptingWolf 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 23 ms 3532 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 3532 KB Output isn't correct
2 Halted 0 ms 0 KB -