oj.uz

답안 #780550

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
780550 2023-07-12T10:06:28 Z NothingXD 휴가 (IOI14_holiday) C++17
100 / 100
 725 ms 13776 KB 
#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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 170 ms 12076 KB Output is correct
2 Correct 89 ms 12364 KB Output is correct
3 Correct 179 ms 12252 KB Output is correct
4 Correct 116 ms 12276 KB Output is correct
5 Correct 226 ms 11204 KB Output is correct
6 Correct 94 ms 11072 KB Output is correct
7 Correct 142 ms 9948 KB Output is correct
8 Correct 168 ms 10008 KB Output is correct
9 Correct 71 ms 11816 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 7892 KB Output is correct
2 Correct 7 ms 7896 KB Output is correct
3 Correct 14 ms 7892 KB Output is correct
4 Correct 13 ms 7892 KB Output is correct
5 Correct 13 ms 7760 KB Output is correct
6 Correct 5 ms 7764 KB Output is correct
7 Correct 5 ms 7764 KB Output is correct
8 Correct 5 ms 7776 KB Output is correct
9 Correct 5 ms 7764 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 177 ms 12828 KB Output is correct
2 Correct 725 ms 13776 KB Output is correct
3 Correct 96 ms 8776 KB Output is correct
4 Correct 10 ms 7764 KB Output is correct
5 Correct 6 ms 7764 KB Output is correct
6 Correct 5 ms 7776 KB Output is correct
7 Correct 5 ms 7780 KB Output is correct
8 Correct 481 ms 10424 KB Output is correct
9 Correct 516 ms 10364 KB Output is correct