제출 #1016356

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016356		AmirAli_H1	휴가 (IOI14_holiday)	C++17	100 / 100	501 ms	8964 KiB

holiday

// In the name of Allah

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

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

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = (1 << 17) + 7;
const int oo = 1e9 + 7;

int n, v, d;
ll a[maxn]; int ind[maxn];
pll t[2 * maxn], A[maxn];
ll res;

pll add_pair(pll a, pll b) {
	return Mp(a.F + b.F, a.S + b.S);
}

void add_val(int v, int tl, int tr, int i, pll x) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] = add_pair(t[v], x);
		return ;
	}
	int mid = (tl + tr) / 2;
	add_val(2 * v + 1, tl, mid, i, x); add_val(2 * v + 2, mid, tr, i, x);
	t[v] = add_pair(t[2 * v + 1], t[2 * v + 2]);
}

ll get_val(int v, int tl, int tr, ll x) {
	x = min(x, t[v].S);
	if (x == 0) return 0;
	if (tr - tl == 1) return t[v].F;
	
	int mid = (tl + tr) / 2;
	if (t[2 * v + 2].S >= x) return get_val(2 * v + 2, mid, tr, x);
	else return t[2 * v + 2].F + get_val(2 * v + 1, tl, mid, x - t[2 * v + 2].S);
}

void get_opt(int l, int r, int lx, int rx) {
	if (r - l < 1) return ;
	
	int mid = (l + r) / 2;
	int j = mid, k = -1; ll valx = -oo;
	
	for (int i = mid; i < min(r, v); i++) add_val(0, 0, n, ind[i], Mp(a[i], 1));
	for (int i = lx; i < rx; i++) {
		add_val(0, 0, n, ind[i], Mp(a[i], 1));
		int R = d - ((i - j) + min(i - v, v - j));
		if (R < 0) break;
		ll x = get_val(0, 0, n, R);
		if (x > valx) {
			k = i; valx = x;
		}
	}
	res = max(res, valx);
	for (int i = lx; i < rx; i++) {
		add_val(0, 0, n, ind[i], Mp(-a[i], -1));
		int R = d - ((i - j) + min(i - v, v - j));
		if (R < 0) break;
	}
	get_opt(l, mid, lx, k + 1);
	for (int i = mid; i < min(r, v); i++) add_val(0, 0, n, ind[i], Mp(-a[i], -1));
	
	for (int i = lx; i < k; i++) add_val(0, 0, n, ind[i], Mp(a[i], 1));
	get_opt(mid + 1, r, k, rx);
	for (int i = lx; i < k; i++) add_val(0, 0, n, ind[i], Mp(-a[i], -1));
}

ll findMaxAttraction(int Nx, int Sx, int Dx, int Ax[]) {
	n = Nx; v = Sx; d = Dx;
	
	for (int i = 0; i < n; i++) {
		a[i] = Ax[i];
		A[i] = Mp(a[i], i);
	}
	sort(A, A + n);
	for (int i = 0; i < n; i++) {
		ind[i] = lower_bound(A, A + n, (pll) Mp(a[i], i)) - A;
	}
	
	res = 0;
	int l = max(0, v - d), r = v + 1;
	int lx = v, rx = min(n, v + d + 1);
	get_opt(l, r, lx, rx);
	return res;
}

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