oj.uz

Submission #208630

# Submission time Handle Problem Language Result Execution time Memory
208630 2020-03-11T23:45:38 Z Sorting Holiday (IOI14_holiday) C++14
100 / 100
 2736 ms 13968 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

const int kN = 1e5 + 7;
const long long inf = 1e18;

pair<long long, int> nodes[4 * kN];
vector<pair<int, int>> order;
vector<int> idx;

pair<long long, int> merge(pair<long long, int> a, pair<long long, int> b){
	pair<long long, int> ret;
	ret.first = a.first + b.first;
	ret.second = a.second + b.second;
	return ret;
}

void update(int idx, int l, int r, int s, int val){
	if(s < l || r < s)
		return;
	if(l == r){
		nodes[idx].second = val;
		nodes[idx].first = order[l].first * nodes[idx].second;
		return;
	}

	int mid = (l + r) >> 1;
	update(2 * idx, l, mid, s, val);
	update(2 * idx + 1, mid + 1, r, s, val);

	nodes[idx] = merge(nodes[2 * idx], nodes[2 * idx + 1]);
}

pair<long long, int> query(int idx, int l, int r, int cnt){
	if(!cnt)
		return {0, 0};
	if(nodes[idx].second <= cnt)
		return nodes[idx];

	int mid = (l + r) >> 1;
	pair<long long, int> b = query(2 * idx + 1, mid + 1, r, cnt);
	pair<long long, int> a = query(2 * idx, l, mid, cnt - b.second);
	
	return merge(a, b);
}

long long val[3 * kN][2], val_rev[3 * kN][2];

void calc(int l, int r, int sl, int sr, int start, int mul, int n){
	if(l > r)
		return;
	if(sl > sr)
		return;

	int mid = (l + r) >> 1;
	int which = (mul - 1);
	long long best = -inf, best_idx = -1;
	for(int i = sl; i <= sr; ++i){
		update(1, 0, n - 1, idx[i], 1);
		long long rem = mid - (i - start) * mul;
		if(rem < 0)
			break;

		long long curr = query(1, 0, n - 1, rem).first;
		if(curr > best){
			best = curr;
			best_idx = i;
		}
	}
	val[mid][which] = best;

	for(int i = sl; i <= sr; ++i)
		update(1, 0, n - 1, idx[i], 0);

	calc(l, mid - 1, sl, best_idx, start, mul, n);

	for(int i = sl; i < best_idx; ++i)
		update(1, 0, n - 1, idx[i], 1);

	calc(mid + 1, r, best_idx, sr, start, mul, n);

	for(int i = sl; i <= sr; ++i)
		update(1, 0, n - 1, idx[i], 0);
}

void calc_rev(int l, int r, int sl, int sr, int start, int mul, int n){
	if(l > r)
		return;
	if(sl > sr)
		return;

	//cout << "calc_rev " << l << " " << r << " " << sl << " " << sr << " " << start << " " << mul << " " << n << endl; 

	int mid = (l + r) >> 1;
	int which = (mul - 1);
	long long best = -inf, best_idx = -1;
	for(int i = sr; i >= sl; --i){
		update(1, 0, n - 1, idx[i], 1);
		long long rem = mid - (start - i) * mul;
		if(rem < 0)
			break;

		long long curr = query(1, 0, n - 1, rem).first;
		if(curr > best){
			best = curr;
			best_idx = i;
		}
	}
	val_rev[mid][which] = best;

	for(int i = sr; i >= sl; --i)
		update(1, 0, n - 1, idx[i], 0);

	calc_rev(l, mid - 1, best_idx, sr, start, mul, n);
	
	for(int i = sr; i > best_idx; --i)
		update(1, 0, n - 1, idx[i], 1);

	calc_rev(mid + 1, r, sl, best_idx, start, mul, n);

	for(int i = sl; i <= sr; ++i)
		update(1, 0, n - 1, idx[i], 0);
}

long long findMaxAttraction(int n, int start, int d, int attraction[]){
	if(d == 0)
		return 0;
	if(d == 1)
		return attraction[start];
	order.resize(n);
	for(int i = 0; i < n; ++i)
		order[i] = {attraction[i], i};
	sort(order.begin(), order.end());

	idx.resize(n);
	for(int i = 0; i < n; ++i)
		idx[order[i].second] = i;

	calc(0, d, start, n - 1, start, 1, n);
	calc(2, d, start + 1, n - 1, start, 2, n);

	calc_rev(0, d, 0, start, start, 1, n);
	calc_rev(2, d, 0, start - 1, start, 2, n);

	//for(int i = 0; i <= d; ++i)
	//	cout << val[i][0] << " " << val[i][1] << " " << val_rev[i][0] << " " << val_rev[i][1] << " val0 val1 val_rev0 val_rev1" << endl;

	long long ans = 0;
	for(int i = 0; i <= d - 2; ++i)
		ans = max(ans, val[i][0] + val_rev[d - i][1]);
	for(int i = 0; i <= d - 2; ++i)
		ans = max(ans, val_rev[i][0] + val[d - i][1]);

	ans = max(ans, val[d][0]);
	ans = max(ans, val_rev[d][0]);

	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2339 ms 12272 KB Output is correct
2 Correct 1959 ms 12408 KB Output is correct
3 Correct 2355 ms 12268 KB Output is correct
4 Correct 1966 ms 12280 KB Output is correct
5 Correct 2464 ms 10232 KB Output is correct
6 Correct 928 ms 7684 KB Output is correct
7 Correct 1327 ms 6136 KB Output is correct
8 Correct 1538 ms 6264 KB Output is correct
9 Correct 754 ms 9208 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 760 KB Output is correct
2 Correct 50 ms 760 KB Output is correct
3 Correct 46 ms 760 KB Output is correct
4 Correct 44 ms 632 KB Output is correct
5 Correct 40 ms 632 KB Output is correct
6 Correct 13 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 12 ms 376 KB Output is correct
9 Correct 12 ms 504 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2446 ms 13956 KB Output is correct
2 Correct 2736 ms 13968 KB Output is correct
3 Correct 654 ms 3576 KB Output is correct
4 Correct 31 ms 504 KB Output is correct
5 Correct 12 ms 376 KB Output is correct
6 Correct 12 ms 376 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 2445 ms 7672 KB Output is correct
9 Correct 2442 ms 7636 KB Output is correct