제출 #780550

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780550		NothingXD	휴가 (IOI14_holiday)	C++17	100 / 100	725 ms	13776 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr << endl;}

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 3e5 + 10;
const int lg = 17;
const ll inf = 1e18;
int d, sz, val[maxn], st;
ll dp[maxn], A[maxn], B[maxn];
vector<int> num;
ll f[2][maxn];

void add(ll *f, int idx, ll x){
	for (; idx <= sz; idx += idx & -idx){
		f[idx] += x;
	}
}

ll get(ll *f, int idx){
	ll res = 0;
	for (; idx; idx -= idx & -idx) res += f[idx];
	return res;
}

ll get(ll *f, int l, int r){
	if (r < l) return 0;
	return get(f, r) - get(f, l-1);
}

int find(ll *f, ll x){
	int idx = 0;
	for (int i = lg-1; ~i; i--){
		int tmp = idx + (1 << i);
		if (tmp <= sz && f[tmp] < x){
			x -= f[tmp];
			idx = tmp;
		}
	}
	return idx + 1;
}

int L = 0, R = -1;

ll get(int l, int r, int k){
	if (k < 0) return -inf;
	if (k == 0) return 0;
	while(R < r){
		R++;
		add(f[0], val[R], 1);
		add(f[1], val[R], num[val[R]-1]);
	}
	while(l < L){
		L--;
		add(f[0], val[L], 1);
		add(f[1], val[L], num[val[L]-1]);
	}
	while(r < R){
		add(f[0], val[R], -1);
		add(f[1], val[R], -num[val[R]-1]);
		R--;
	}

	while(L < l){
		add(f[0], val[L], -1);
		add(f[1], val[L], -num[val[L]-1]);
		L++;
	}

	int tmp = get(f[0], sz);
	if (r - l + 1 <= k) return get(f[1], sz);
	int idx = find(f[0], (r - l + 1) - k);
	tmp = get(f[0], idx + 1, sz);
	ll res = get(f[1], idx + 1, sz) + 1ll * (k-tmp) * num[idx-1];
	return res;
}

void solve(int t, int l, int r, int ql, int qr){
	if (r < l || qr < ql) return;
	int mid = (l + r) >> 1;
	if (t == 0) dp[mid] = get(ql, st-1, mid - (st - ql));
	else dp[mid] = get(st, ql, mid - (ql - st));
	int idx = ql;
	for (int i = ql + 1; i <= qr; i++){
		ll tmp;
	   	if (t == 0) tmp = get(i, st-1, mid - (st - i));
		else tmp = get(st, i, mid - (i - st));
		if (tmp > dp[mid]){
			dp[mid] = tmp;
			idx = i;
		}
	}
	if (t == 0){
		solve(t, l, mid-1, idx, qr);
		solve(t, mid+1, r, ql, idx);
	}
	else{
		solve(t, l, mid-1, ql, idx);
		solve(t, mid+1, r, idx, qr);
	}
}

ll findMaxAttraction(int n, int start, int _d, int a[]) {

	st = start;

	d = _d;

	for (int i = 0; i < n; i++){
		num.push_back(a[i]);
	}

	num.push_back(0);
	sort(all(num));
	num.resize(distance(num.begin(), unique(all(num))));

	for (int i = 0; i < n; i++){
		a[i] = lower_bound(all(num), a[i]) - num.begin() + 1;
	}

	sz = num.size();


	for (int i = 0; i < start; i++){
		val[2*i] = a[i];
		val[2*i+1] = 1;
	}

	for (int i = start; i < n; i++){
		val[start + i] = a[i];
	}



	st = 2*start;

	solve(0, 1, d, 0, st-1);
	for (int i = 1; i <= d; i++) A[i] = dp[i];
	memset(dp, 0, sizeof dp);
	solve(1, 1, d, st, n+start-1);
	for (int i = 1; i <= d; i++) B[i] = dp[i];

	ll ans = 0;
	for (int i = 0; i <= d; i++){
		ans = max(ans, A[i] + B[d-i]);
	}

	for (int i = 0; i <= start; i++){
		val[i] = a[i];
	}
	for (int i = start+1; i < n; i++){
		val[2*i-start] = a[i];
		val[2*i-start-1] = 1;
	}
	
	memset(f, 0, sizeof f);
	L = 0, R = -1;

	memset(dp, 0, sizeof dp);

	st = start;

	solve(0, 1, d, 0, st-1);
	for (int i = 1; i <= d; i++) A[i] = dp[i];
	memset(dp, 0, sizeof dp);
	solve(1, 1, d, st, 2*(n-1)-start);
	for (int i = 1; i <= d; i++) B[i] = dp[i];
	for (int i = 0; i <= d; i++){
		ans = max(ans, A[i] + B[d-i]);
	}
    return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53