제출 #483602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483602		pavement	Holiday (IOI14_holiday)	C++17	24 / 100	5087 ms	7768 KiB

holiday

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

#define mp make_pair
#define pb push_back
typedef long long ll;

int n, start, d, a[100005], b[100005], rev[100005];
vector<int> disc, vec[100005];
ll ans;

int cnt(vector<pair<int, ll> > val, int l, int r) {
	return upper_bound(val.begin(), val.end(), mp(r, (ll)1e16)) - lower_bound(val.begin(), val.end(), mp(l, 0ll));
}

ll sum(vector<pair<int, ll> > val, int l, int r) {
	int p2 = upper_bound(val.begin(), val.end(), mp(r, (ll)1e16)) - val.begin();
	if (p2 == 0) return 0;
	p2--;
	int p1 = lower_bound(val.begin(), val.end(), mp(l, 0ll)) - val.begin();
	return val[p2].second - (p1 ? val[p1 - 1].second : 0ll);
}

struct node {
	node *left, *right;
	int S, E;
	vector<pair<int, ll> > val;
	node(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			sort(vec[S].begin(), vec[S].end());
			val.resize(vec[S].size());
			ll prf = 0;
			for (int j = 0; j < vec[S].size(); j++) {
				prf += a[vec[S][j]];
				val[j] = mp(vec[S][j], prf);
			}
			return;
		}
		int M = (S + E) >> 1;
		left = new node(S, M);
		right = new node(M + 1, E);
		merge(left->val.begin(), left->val.end(), right->val.begin(), right->val.end(), back_inserter(val));
		ll prf = 0;
		for (int j = 0; j < val.size(); j++) {
			prf += a[val[j].first];
			val[j].second = prf;
		}
	}
	ll qry(int l, int r, int k) { // sum of k largest elements in [l, r]
		if (S == E) return (ll)min(cnt(val, l, r), k) * (ll)rev[S];
		if (cnt(right->val, l, r) >= k) return right->qry(l, r, k);
		else {
			ll ans = left->qry(l, r, k - cnt(right->val, l, r));
			assert(ans >= 0);
			return ans + sum(right->val, l, r);
		}
	}
} *root;

void dnc(int l, int r, int x, int y) {
	if (l > r || x > y) return;
	int m = (l + r) >> 1, opt = -1;
	ll cur = -1;
	for (int i = x; i <= y; i++) {
		if (d - 2 * (start - m) - (i - start) < 0) break;
		ll tmp = root->qry(m, i, d - 2 * (start - m) - (i - start));
		assert(tmp >= 0);
		if (tmp > cur) {
			cur = tmp;
			opt = i;
		}
	}
	ans = max(ans, cur);
	assert(opt != -1);
	dnc(l, m - 1, x, opt);
	dnc(m + 1, r, opt, y);
}

ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
	n = _n;
	start = _start;
	d = _d;
	for (int i = 0; i < n; i++) {
		a[i] = _attraction[i];
		disc.pb(a[i]);
	}
	sort(disc.begin(), disc.end());
	disc.erase(unique(disc.begin(), disc.end()), disc.end());
	for (int i = 0; i < n; i++) {
		b[i] = lower_bound(disc.begin(), disc.end(), a[i]) - disc.begin() + 1;
		vec[b[i]].pb(i);
		rev[b[i]] = a[i];
	}
	root = new node(1, disc.size());
	for (int i = 0; i < n; i++) {
		if (abs(i - start) > d) break;
		ans = max(ans, root->qry(min(i, start), max(i, start), d - abs(i - start)));
	}
	dnc(max(0, start - d / 2), start, start, n - 1);
	reverse(a, a + n);
	start = n - start - 1;
	for (int i = 1; i <= disc.size(); i++) vec[i].clear();
	for (int i = 0; i < n; i++) {
		b[i] = lower_bound(disc.begin(), disc.end(), a[i]) - disc.begin() + 1;
		vec[b[i]].pb(i);
		rev[b[i]] = a[i];
	}
	root = new node(1, disc.size());
	dnc(max(0, start - d / 2), start, start, n - 1);
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In constructor 'node::node(int, int)':
holiday.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for (int j = 0; j < vec[S].size(); j++) {
      |                    ~~^~~~~~~~~~~~~~~
holiday.cpp:45:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   for (int j = 0; j < val.size(); j++) {
      |                   ~~^~~~~~~~~~~~
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 1; i <= disc.size(); i++) vec[i].clear();
      |                  ~~^~~~~~~~~~~~~~

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