oj.uz

Submission #222220

# Submission time Handle Problem Language Result Execution time Memory
222220 2020-04-12T11:39:31 Z DystoriaX Holiday (IOI14_holiday) C++14
100 / 100
 916 ms 13032 KB 
#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

struct Node{
	long long val = 0;
	int active = 0;
};

int n;
Node st[400010];
long long int ans;
int idx[300010];
vector<pair<int, int> > v;

long long f[300010], g[300010];
int optF[300010], optG[300010];

void update(int l, int r, int pt, bool val, int i){
	if(pt < l || r < pt) return;

	if(l == r && l == pt){
		st[i].active = val;

		if(st[i].active) st[i].val = v[l].first;
		else st[i].val = 0;

		return;
	}

	int m = (l + r) >> 1;

	update(l, m, pt, val, i << 1);
	update(m + 1, r, pt, val, 1 + (i << 1));

	st[i].val = st[i << 1].val + st[1 + (i << 1)].val;
	st[i].active = st[i << 1].active + st[1 + (i << 1)].active;
}

long long query(int l, int r, int val, int i){
	if(val == 0) return 0;
	if(st[i].active <= val) return st[i].val;

	int m = (l + r) >> 1;

	return query(l, m, min(val, st[i << 1].active), i << 1) + query(m + 1, r, max(0, val - st[i << 1].active), 1 + (i << 1));
}

void update(int pt, bool val){
	update(0, n - 1, pt, val, 1);
}

long long query(int val){
	if(val <= 0) return 0;
	return query(0, n - 1, val, 1);
}

int now;

void solve(int l, int r, int optL, int optR, int pvt){
	if(l > r) return;

	long long val = -1;
	int opt = -1;

	int m = (l + r) >> 1;

	while(now < optL) update(idx[++now], 1);
	while(now > optL) update(idx[now--], 0);

	for(int i = optL; i <= optR; i++){
		if(now < i) update(idx[++now], 1);

		long long x = query(m - (i - pvt));

		if(x > val){
			val = x;
			opt = i;
		}
	}

	f[m] = val;
	optF[m] = opt;

	solve(l, m - 1, optL, opt, pvt);
	solve(m + 1, r, opt, optR, pvt);
}

void solveS(int l, int r, int optL, int optR, int pvt){
	if(l > r) return;

	long long val = -1;
	int opt = -1;

	int m = (l + r) >> 1;

	while(now > optR) update(idx[--now], 1);
	while(now < optR) update(idx[now++], 0);

	for(int i = optR; i >= optL; i--){
		if(now > i) update(idx[--now], 1);

		long long x = query(m - (pvt - i));

		if(x > val){
			val = x;
			opt = i;
		}
	}

	g[m] = val;
	optG[m] = opt;

	solveS(l, m - 1, opt, optR, pvt);
	solveS(m + 1, r, optL, opt, pvt);
}

long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
	n = N;
	for(int i = 0; i < n; i++) v.emplace_back(attraction[i], i);

	sort(v.rbegin(), v.rend());

	for(int i = 0; i < n; i++){
		idx[v[i].second] = i;
	}

	now = start - 1;
	solve(0, d, start, n - 1, start);

	while(now >= start) update(idx[now--], 0);
	now = start;

	if(start > 0) solveS(0, d, 0, start - 1, start - 1);

	for(int i = 1; i <= d; i++){
		// cout << i << " -> " << g[i] << " " << optG[i] << endl;
		ans = max(ans, max(f[i], g[i - 1]));

		if(d - i - (optF[i] - start) - 1 > 0) ans = max(ans, f[i] + g[d - i - (optF[i] - start) - 1]);
		if(d - (i + 1) - (start - 1 - optG[i]) - 1 > 0) ans = max(ans, g[i] + f[d - i - (start - optG[i]) - 1]);
	}

    return ans;
}

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 6 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 726 ms 8808 KB Output is correct
2 Correct 651 ms 8684 KB Output is correct
3 Correct 744 ms 8684 KB Output is correct
4 Correct 673 ms 8860 KB Output is correct
5 Correct 870 ms 8040 KB Output is correct
6 Correct 255 ms 4212 KB Output is correct
7 Correct 459 ms 4588 KB Output is correct
8 Correct 572 ms 4936 KB Output is correct
9 Correct 173 ms 4724 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 668 ms 13032 KB Output is correct
2 Correct 789 ms 10220 KB Output is correct
3 Correct 284 ms 3952 KB Output is correct
4 Correct 15 ms 640 KB Output is correct
5 Correct 7 ms 384 KB Output is correct
6 Correct 7 ms 384 KB Output is correct
7 Correct 8 ms 384 KB Output is correct
8 Correct 872 ms 8200 KB Output is correct
9 Correct 916 ms 8172 KB Output is correct