oj.uz

Submission #245341

# Submission time Handle Problem Language Result Execution time Memory
245341 2020-07-06T04:59:50 Z vioalbert Holiday (IOI14_holiday) C++14
100 / 100
 1559 ms 15852 KB 
#include <bits/stdc++.h>
#include"holiday.h"
using namespace std;
typedef long long ll;

const int N = 1e5+5;
int n, start, d;
ll attraction[N], dp[N];
map<ll, int> cidx;
vector<ll> cval;

int walk(int l, int r) {
	return r-l + min(start-l, r-start);
}

struct SegmentTree {
	int n, l, r;
	vector<ll> sum, cnt;
	SegmentTree(int _n) : n(_n), l(0), r(-1) {
		sum.assign(4*n, 0);
		cnt.assign(4*n, 0);
	}
	void update(int idx, int l, int r, int x, ll val) {
		if(r < x || x < l) return;
		else if(l == r) {
			sum[idx] += cval[l] * val;
			cnt[idx] += val;
			return;
		}
		int lc = idx<<1, rc = lc|1;
		update(lc, l, (l+r)/2, x, val);
		update(rc, (l+r)/2+1, r, x, val);
		sum[idx] = sum[lc] + sum[rc];
		cnt[idx] = cnt[lc] + cnt[rc];
	}
	ll queryKth(int idx, int l, int r, int k) {
		if(k <= 0 || l > r) return 0;
		if(cnt[idx] <= k) return sum[idx];
		if(l == r) return k * cval[l];
		int mid = (l+r)/2, lc = idx<<1, rc = lc|1;
		if(k <= cnt[rc])
			return queryKth(rc, mid+1, r, k);
		else
			return queryKth(rc, mid+1, r, cnt[rc]) + queryKth(lc, l, mid, k-cnt[rc]);
	}
};
SegmentTree *st;

ll cost(int l, int r, int k) {
	if(k <= 0) return 0;
	while(st->r < r) st->update(1, 0, n-1, cidx[attraction[++st->r]], 1);
	while(st->r > r) st->update(1, 0, n-1, cidx[attraction[st->r--]], -1);
	while(st->l > l) st->update(1, 0, n-1, cidx[attraction[--st->l]], 1);
	while(st->l < l) st->update(1, 0, n-1, cidx[attraction[st->l++]], -1);
	return st->queryKth(1, 0, n-1, k);
}

void solve(int l, int r, int optL, int optR) {
	if(l > r) return;
	int mid = (l+r)>>1, best = -1;
	ll& ret = dp[mid] = -1e15;
	for(int i = optL; i <= optR; i++) {
		ll cur = cost(mid, i, d - walk(mid, i));
		if(ret < cur)
			ret = cur, best = i;
	}
	solve(l, mid-1, optL, best);
	solve(mid+1, r, best, optR);
}

ll findMaxAttraction(int _n, int _start, int _d, int _attraction[]) {
	n = _n, start = _start, d = _d;
	for(int i = 0; i < n; i++)
		attraction[i] = _attraction[i];

	for(int i = 0; i < n; i++)
		cval.push_back(attraction[i]);
	sort(cval.begin(), cval.end());
	auto it = unique(cval.begin(), cval.end());
	cval.erase(it, cval.end());
	for(int i = 0; i < cval.size(); i++)
		cidx[cval[i]] = i;

	st = new SegmentTree(n);
	solve(0, start, start, n-1);
	ll ans = 0;
	for(int i = 0; i <= start; i++)
		ans = max(ans, dp[i]);
	return ans;
}

Compilation message

holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < cval.size(); i++)
                 ~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory 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 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 8820 KB Output is correct
2 Correct 43 ms 8920 KB Output is correct
3 Correct 44 ms 8820 KB Output is correct
4 Correct 41 ms 8820 KB Output is correct
5 Correct 48 ms 8308 KB Output is correct
6 Correct 15 ms 2812 KB Output is correct
7 Correct 27 ms 4856 KB Output is correct
8 Correct 32 ms 5752 KB Output is correct
9 Correct 13 ms 2172 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 768 KB Output is correct
2 Correct 7 ms 640 KB Output is correct
3 Correct 9 ms 768 KB Output is correct
4 Correct 18 ms 768 KB Output is correct
5 Correct 12 ms 768 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 6 ms 384 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 10348 KB Output is correct
2 Correct 80 ms 15852 KB Output is correct
3 Correct 228 ms 7544 KB Output is correct
4 Correct 13 ms 768 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 512 KB Output is correct
7 Correct 7 ms 384 KB Output is correct
8 Correct 1559 ms 15592 KB Output is correct
9 Correct 1477 ms 15364 KB Output is correct