oj.uz

답안 #244731

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
244731 2020-07-04T19:04:37 Z Berted 휴가 (IOI14_holiday) C++14
100 / 100
 935 ms 7392 KB 
#include "holiday.h"
#include <iostream>
#include <vector>
#include <map>
#include <bitset>
#include <algorithm>
#include <assert.h>
#define ll long long
#define pii pair<int, int>
#define fst first
#define snd second
const ll MN = -1e18;
const int SZ = 1 << 18;

using namespace std;

int n, s, d, ar[100001], idx[100001];
bitset<100001> used;
pii srt[100001] = {};
ll seg[SZ][2] = {}, ret = 0;

void bld(int idx, int L, int R)
{
	//cout << "B " << idx << " " << L << " " << R << "\n";
	seg[idx][0] = seg[idx][1] = 0; 
	if (L < R)
	{
		int M = L + R >> 1;
		bld(2 * idx, L, M); bld(2 * idx + 1, M + 1, R);
	}
	else {used[L] = 0;}
}

inline void upd(int idx, int L, int R, int x)
{
	if (L <= R)
	{
		if (L == R)
		{
			if (seg[idx][1]) {seg[idx][0] = 0; seg[idx][1] = 0; used[L] = 0;}
			else {seg[idx][1] = 1; seg[idx][0] = srt[L].fst; used[L] = 1;}
		}
		else
		{
			int M = L + R >> 1;
			if (x <= M) upd(2 * idx, L, M, x);
			else upd(2 * idx + 1, M + 1, R, x);
			seg[idx][0] = seg[2 * idx][0] + seg[2 * idx + 1][0];
			seg[idx][1] = seg[2 * idx][1] + seg[2 * idx + 1][1];
		}
		//cout << "U " << L << " " << R << " - " << x << " -- " << seg[idx][0] << " " << seg[idx][1] << "\n";
	}
}

inline ll qry(int idx, int L, int R, int k)
{
	if (k <= 0) return 0;
	if (L <= R)
	{
		//cout << "Q " << L << " " << R << " " << k << "\n";
		if (L == R) {return seg[idx][0];}
		else
		{
			int M = L + R >> 1;
			if (seg[2 * idx][1] >= k) return qry(2 * idx, L, M, k);
			else return qry(2 * idx + 1, M + 1, R, k - seg[2 * idx][1]) + seg[2 * idx][0];
		}
	}
}

void computeL(int l, int r, int p, int optL, int optR)
{
	if (l <= r)
	{
		int m = l + r >> 1;
		//cout << "CL " << l << " " << r << " " << p << " " << optL << " " << optR << "\n";

		if (m < p) {for (int i = m; i < p; i++) upd(1, 0, n - 1, idx[i]);}
		else {for (int i = p; i < m; i++) upd(1, 0, n - 1, idx[i]);}

		ll optVal = 0, optP = optL, cr;
		for (int i = optL; i <= optR; i++)
		{
			if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
			//cout << i << " " << d - 2 * (s - m) - (i - s) << "\n";
			cr = qry(1, 0, n - 1, d - 2 * (s - m) - (i - s));
			//cout << cr << "\n";
			if (cr > optVal) {optVal = cr; optP = i;}
		}
		for (int i = optL; i <= optR; i++) {upd(1, 0, n - 1, idx[i]);}
		ret = max(ret, optVal);

		computeL(l, m - 1, m, optL, optP);
		computeL(m + 1, r, m, optP, optR);

		if (m < p) {for (int i = m; i < p; i++) upd(1, 0, n - 1, idx[i]);}
		else {for (int i = p; i < m; i++) upd(1, 0, n - 1, idx[i]);}
	}
	else
	{
		for (int i = optL; i <= optR; i++) 
		{
			if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
		}
	}
}

void computeR(int l, int r, int p, int optL, int optR)
{
	if (l <= r)
	{
		int m = l + r >> 1;

		//cout << "CR " << l << " " << r << " " << optL << " " << optR << "\n";

		if (m > p) for (int i = m; i > p; i--) upd(1, 0, n - 1, idx[i]);
		else for (int i = p; i > m; i--) upd(1, 0, n - 1, idx[i]);

		ll optVal = 0, optP = optR, cr;
		for (int i = optR; i >= optL; i--)
		{
			if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
			cr = qry(1, 0, n - 1, d - 2 * (m - s) - (s - i));
			//cout << i << " " << d - 2 * (m - s) - (s - i) << "\n";
			//cout << cr << "\n";
			if (cr > optVal) {optVal = cr; optP = i;}
		}
		for (int i = optR; i >= optL; i--) {upd(1, 0, n - 1, idx[i]);}
		ret = max(ret, optVal);

		computeR(m + 1, r, m, optP, optR);
		computeR(l, m - 1, m, optL, optP);

		if (m > p) for (int i = m; i > p; i--) upd(1, 0, n - 1, idx[i]);
		else for (int i = p; i > m; i--) upd(1, 0, n - 1, idx[i]);
	}
	else
	{
		for (int i = optR; i >= optL; i--) 
		{
			if (!used[idx[i]]) upd(1, 0, n - 1, idx[i]);
		}
	}
}

ll findMaxAttraction(int N, int S, int D, int A[]) 
{
	n = N; d = D; s = S;
	for (int i = 0; i < n; i++) {ar[i] = A[i]; srt[i] = make_pair(A[i], i);}
	sort(srt, srt + n, greater<pii>());
	for (int i = 0; i < n; i++) 
	{
		idx[srt[i].snd] = i;
		//cout << srt[i].snd << " -> " << i << "\n";
	}
	
	//cout << "Here\n";

	if (d) ret = ar[s];

	bld(1, 0, n - 1);
	computeL(0, s, s + 1, s + 1, n - 1);
	bld(1, 0, n - 1);
	computeR(s, n - 1, s - 1, 0, s - 1);

	return ret;
}




/*
const int SZ = 1 << 17;
int n, fwk[2][SZ + 1] = {};
long long dp[2][9001] = {}, mxL[9001] = {}, mxR[9001] = {}, mxcL[9001] = {}, mxcR[9001] = {};
map<pair<int, int>, int> mp;

inline void upd(int t, int x, int v)
{
	for (; x < SZ; x += x & (-x)) fwk[t][x] += v;
}

inline int qry(int t, int x)
{
	int ret = 0;
	for (; x; x -= x & (-x)) ret += fwk[t][x];
	return ret; 
}

inline int fd(int x)
{
	int to = 0, pv = 0;
	for (int i = SZ >> 1; i; i >>= 1)
	{
		//cout << i << " " << pv << " " << fwk[0][i + pv] << " " << to << " " << x << "\n";
		if (to + fwk[0][i + pv] <= x) {to += fwk[0][i + pv]; pv += i;}
	}
	return pv;
}

 
long long int findMaxAttraction(int N, int S, int D, int A[]) { //Sub - 2
	assert(S == 0);
	n = N;
	for (int i = 0; i < n; i++) {mp[make_pair(A[i], i)] = 1;}
	int p = n;
	long long int ans = 0;
	for (auto &x : mp) {x.second = p--;}
	for (int i = 0; i < min(D + 1, n); i++)
	{
		upd(0, mp[make_pair(A[i], i)], 1);
		upd(1, mp[make_pair(A[i], i)], A[i]);
		int idx = fd(D - i);
		ans = max(ans, (long long)qry(1, idx));
	}
    return ans;
}

long long int findMaxAttraction(int N, int S, int D, int A[]) { //Sub 1-3
	assert(n <= 3000);
	n = N;
	ll ans = 0;
	for (int i = 0; i <= D; i++) dp[S & 1][i] = MN;
	dp[S & 1][0] = 0;
	dp[S & 1][1] = A[S];
	mxL[1] = A[S];
	for (int i = S - 1; i >= 0; i--)
	{
		int ns = i & 1, os = !ns;
		for (int k = 0; k < (S - i); k++) dp[ns][k] = MN;
		for (int k = S - i; k <= D; k++)
		{
			dp[ns][k] = MN;
			dp[ns][k] = max(dp[ns][k - 1], dp[os][k - 1]);
			if (k > 1)
			{
				dp[ns][k] = max(dp[ns][k], dp[os][k - 2] + A[i]);
			}
			mxL[k] = max(mxL[k], dp[ns][k]);
		}
	}
	for (int i = 0; i <= D; i++) dp[S & 1][i] = MN;
	dp[S & 1][0] = 0;
	dp[S & 1][1] = A[S];
	mxcL[1] = A[S];
	for (int i = S - 1; i >= 0; i--)
	{
		int ns = i & 1, os = !ns;
		for (int k = 0; k < 2 * (S - i); k++) dp[ns][k] = MN;
		for (int k = 2 * (S - i); k <= D; k++)
		{
			dp[ns][k] = MN;
			dp[ns][k] = max(dp[ns][k - 2], dp[os][k - 2]);
			if (k > 2)
			{
				dp[ns][k] = max(dp[ns][k], dp[os][k - 3] + A[i]);
			}
			mxcL[k] = max(mxcL[k], dp[ns][k]);
		}
	}
	for (int i = 0; i <= D; i++) dp[~S & 1][i] = MN;
	dp[~S & 1][1] = 0;
	dp[~S & 1][2] = A[S + 1];
	mxR[2] = A[S + 1];
	for (int i = S + 2; i < n; i++)
	{
		int ns = i & 1, os = !ns;
		for (int k = 0; k < i - S; k++) dp[ns][k] = MN;
		for (int k = (i - S); k <= D; k++)
		{
			dp[ns][k] = max(dp[ns][k - 1], dp[os][k - 1]);
			if (k > 1)
			{
				dp[ns][k] = max(dp[ns][k], dp[os][k - 2] + A[i]);
			}
			mxR[k] = max(mxR[k], dp[ns][k]);
			//cout << "DPR " << i << " " << k << " " << dp[ns][k] << " " << mxR[k] << "\n";
		}
	}
	for (int i = 0; i <= D; i++) dp[~S & 1][i] = MN;
	dp[~S & 1][2] = 0;
	dp[~S & 1][3] = A[S + 1];
	mxcR[3] = A[S + 1];
	for (int i = S + 2; i < n; i++)
	{
		int ns = i & 1, os = !ns;
		for (int k = 0; k < 2 * (i - S); k++) dp[ns][k] = MN;
		for (int k = 2 * (i - S); k <= D; k++)
		{
			dp[ns][k] = MN;
			dp[ns][k] = max(dp[ns][k - 2], dp[os][k - 2]);
			if (k > 2)
			{
				dp[ns][k] = max(dp[ns][k], dp[os][k - 3] + A[i]);
			}
			mxcR[k] = max(mxcR[k], dp[ns][k]);
		}
	}
	for (int i = 0; i <= D; i++)
	{
		ans = max(ans, mxcR[i] + mxL[D - i]);
		ans = max(ans, mxcL[i] + mxR[D - i]);
		//cout << i << " " << mxcR[i] << " " << mxL[D - i] << " " << mxcL[i] << " " << mxR[D - i] << "\n";
	}
    return ans;
}
*/

Compilation message

holiday.cpp: In function 'void bld(int, int, int)':
holiday.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int M = L + R >> 1;
           ~~^~~
holiday.cpp: In function 'void upd(int, int, int, int)':
holiday.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M = L + R >> 1;
            ~~^~~
holiday.cpp: In function 'long long int qry(int, int, int, int)':
holiday.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int M = L + R >> 1;
            ~~^~~
holiday.cpp: In function 'void computeL(int, int, int, int, int)':
holiday.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
holiday.cpp: In function 'void computeR(int, int, int, int, int)':
holiday.cpp:112:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1;
           ~~^~~
holiday.cpp: In function 'long long int qry(int, int, int, int)':
holiday.cpp:69:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 229 ms 6648 KB Output is correct
2 Correct 230 ms 6632 KB Output is correct
3 Correct 229 ms 6528 KB Output is correct
4 Correct 233 ms 6648 KB Output is correct
5 Correct 311 ms 6676 KB Output is correct
6 Correct 84 ms 2056 KB Output is correct
7 Correct 155 ms 3584 KB Output is correct
8 Correct 193 ms 3840 KB Output is correct
9 Correct 57 ms 1912 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 11 ms 512 KB Output is correct
3 Correct 9 ms 640 KB Output is correct
4 Correct 16 ms 512 KB Output is correct
5 Correct 15 ms 512 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 8 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 7392 KB Output is correct
2 Correct 230 ms 7296 KB Output is correct
3 Correct 320 ms 3832 KB Output is correct
4 Correct 17 ms 512 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 8 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 910 ms 7160 KB Output is correct
9 Correct 935 ms 7288 KB Output is correct