oj.uz

답안 #129057

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129057 2019-07-11T13:54:36 Z Lawliet 휴가 (IOI14_holiday) C++14
100 / 100
 1006 ms 62712 KB 
#include <bits/stdc++.h>

#define MAX 100010
#define MAXV 1000000010

using namespace std;
typedef long long int lli;

class PersistentSegmentTree
{
	public:

		void copy(int node)
		{
			e.push_back( e[node] );
			d.push_back( d[node] );

			qtd.push_back( qtd[node] );

			sum.push_back( sum[node] );
		}

		int update(int node, int l, int r, int i)
		{
			int newNode = ++curNode;
			copy( node );

			if(l == r)
			{
				qtd[newNode]++;
				sum[newNode] += i;

				return newNode;
			}

			int m = (l + r)/2;

			if(i <= m)
			{
				int aux = update(e[newNode] , l , m , i);
				e[newNode] = aux;
			}
			else
			{
				int aux = update(d[newNode] , m + 1 , r , i);
				d[newNode] = aux;
			}

			qtd[newNode] = qtd[ e[newNode] ] + qtd[ d[newNode] ];
			sum[newNode] = sum[ e[newNode] ] + sum[ d[newNode] ];

			return newNode;
		}

		lli bs(int nodeL, int nodeR, int l, int r, lli k)
		{
			if(l == r) return k*l;

			int m = (l + r)/2;

			int qtdRight = qtd[ d[nodeR] ] - qtd[ d[nodeL] ];
			lli sumRight = sum[ d[nodeR] ] - sum[ d[nodeL] ];

			if(k <= qtdRight) return bs(d[nodeL] , d[nodeR] , m + 1 , r , k);
			return bs(e[nodeL] , e[nodeR] , l , m , k - qtdRight) + sumRight;
		}

		lli getHighests(int l, int r, int k)
		{
			if(k == 0) return 0;

			int qtdInterval = qtd[ root[r] ] - qtd[ root[l - 1] ];
			lli sumInterval = sum[ root[r] ] - sum[ root[l - 1] ];

			if(k >= qtdInterval) return sumInterval;

			return bs(root[l - 1] , root[r] , 0 , MAXV , k);
		}

		void update(int v)
		{
			curVersion++;

			root[curVersion] = update(root[curVersion - 1] , 0 , MAXV , v);
		}

		void init()
		{
			e.clear(); d.clear();
			qtd.clear(); sum.clear();

			e.push_back( 0 ); d.push_back( 0 );
			qtd.push_back( 0 ); sum.push_back( 0LL );

			copy( 0 );

			root[0] = 1;

			curNode = 1;
			curVersion = 0;
		}

	private:

		int curNode;
		int curVersion;

		int root[MAX];

		vector<int> e, d;
		vector<int> qtd;

		vector<lli> sum;
};

int N, S, D;

lli ans;

PersistentSegmentTree SEG;

void DivAndConquer(int l, int r, int optmin, int optmax)
{
	if(l > r) return;

	int mid = (l + r)/2;

	int optInd = optmin;
	lli optAns = -1;

	for(int g = optmin ; g <= optmax ; g++)
	{
		int walkDays = (S - mid) + (g - mid);

		if(walkDays < 0) continue;

		lli curAns = SEG.getHighests(mid , g , D - walkDays);

		if(curAns > optAns)
		{
			optInd = g;
			optAns = curAns;
		}
	}

	ans = max(ans , optAns);

	DivAndConquer(l , mid - 1 , optmin , optInd);
	DivAndConquer(mid + 1 , r , optInd , optmax);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
	N = n; S = start + 1; D = d;

	SEG.init();

	for(int g = 0 ; g < n ; g++)
		SEG.update( attraction[g] );

	DivAndConquer(1 , S , S , N);

	SEG.init();

	for(int g = n - 1 ; g >= 0 ; g--)
		SEG.update( attraction[g] );

	S = N - S + 1;

	DivAndConquer(1 , S , S , N);

	return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 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 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 61988 KB Output is correct
2 Correct 265 ms 62100 KB Output is correct
3 Correct 259 ms 61940 KB Output is correct
4 Correct 264 ms 62068 KB Output is correct
5 Correct 257 ms 58908 KB Output is correct
6 Correct 71 ms 17808 KB Output is correct
7 Correct 136 ms 31960 KB Output is correct
8 Correct 158 ms 38552 KB Output is correct
9 Correct 55 ms 15004 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2272 KB Output is correct
2 Correct 9 ms 2276 KB Output is correct
3 Correct 10 ms 2268 KB Output is correct
4 Correct 16 ms 2272 KB Output is correct
5 Correct 14 ms 2396 KB Output is correct
6 Correct 5 ms 1148 KB Output is correct
7 Correct 6 ms 1144 KB Output is correct
8 Correct 6 ms 1268 KB Output is correct
9 Correct 5 ms 1144 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 277 ms 61984 KB Output is correct
2 Correct 278 ms 61828 KB Output is correct
3 Correct 334 ms 29548 KB Output is correct
4 Correct 16 ms 2400 KB Output is correct
5 Correct 6 ms 1144 KB Output is correct
6 Correct 6 ms 1268 KB Output is correct
7 Correct 6 ms 1268 KB Output is correct
8 Correct 1006 ms 62712 KB Output is correct
9 Correct 980 ms 62688 KB Output is correct