oj.uz

Submission #134641

# Submission time Handle Problem Language Result Execution time Memory
134641 2019-07-23T06:14:06 Z mirbek01 Holiday (IOI14_holiday) C++11
100 / 100
 259 ms 49520 KB 
#include "holiday.h"
//#include "grader.cpp"
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 2;

struct st{
	int l, r, cnt;
	long long sum;
	st(){
		l = r = cnt = sum = 0;
	}
}t[N * 20];

int d, start, sz;
long long ans;
vector <int> vec;
int root[N], cn;

void upd(int ov, int v, int pos, int tl = 0, int tr = sz){
	if(tl == tr){
		t[v].sum = t[ov].sum + vec[tl];
		t[v].cnt = t[ov].cnt + 1;
	} else {
		int tm = (tl + tr) >> 1;
		if(pos <= tm){
			if(!t[v].l) t[v].l = ++ cn;
			t[v].r = t[ov].r;
			upd(t[ov].l, t[v].l, pos, tl, tm);
		} else{
			if(!t[v].r) t[v].r = ++ cn;
			t[v].l = t[ov].l;
			upd(t[ov].r, t[v].r, pos, tm + 1, tr);
		}
		t[v].cnt = t[ t[v].l ].cnt + t[ t[v].r ].cnt;
		t[v].sum = t[ t[v].l ].sum + t[ t[v].r ].sum;   
	}
}

long long get(int ov, int v, int cnt, int tl = 0, int tr = sz){
	if(cnt <= 0) return 0ll;
	if(tl == tr){
		long long k = min(t[v].cnt - t[ov].cnt, cnt);
		return k * 1ll * vec[tl];
	}
	int tm = (tl + tr) >> 1;
	int k = t[ t[v].r ].cnt - t[ t[ov].r ].cnt;
	if(k <= cnt)
		return t[ t[v].r ].sum - t[ t[ov].r ].sum + get(t[ov].l, t[v].l, cnt - k, tl, tm);
	return get(t[ov].r, t[v].r, cnt, tm + 1, tr);
}

void calc(int l, int r, int opl, int opr){
	if(l > r) return ;
	int md = (l + r) >> 1, opt = -1;
	long long ret = -1;
	for(int i = opl; i <= opr; i ++){
		int lenA = (start - md), lenB = (i - start);
		int cnt = d - lenA - lenB - min(lenA, lenB);
		long long now = get(root[md], root[i + 1], cnt);
		if(ret < now){
			ret = now;
			opt = i;
		}
	}
	ans = max(ans, ret);
	calc(l, md - 1, opl, opt);
	calc(md + 1, r, opt, opr);
}

long long int findMaxAttraction(int n, int startS, int D, int ar[]) {
	d = D;
	start = startS;
	vec.push_back(-2e9);
	for(int i = 0; i < n; i ++){
		vec.push_back(ar[i]);
	}
	sort(vec.begin(),vec.end());
	vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
	sz = (int)vec.size() - 1;
	for(int i = 0; i < n; i ++){
		ar[i] = lower_bound(vec.begin(),vec.end(), ar[i])-vec.begin();
	}
	for(int i = 1; i <= n; i ++){
		root[i] = ++ cn;
		upd(root[i - 1], root[i], ar[i - 1]);
	}
	calc(0, start, start, n);
	return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 47244 KB Output is correct
2 Correct 45 ms 47316 KB Output is correct
3 Correct 41 ms 47224 KB Output is correct
4 Correct 41 ms 47268 KB Output is correct
5 Correct 41 ms 47224 KB Output is correct
6 Correct 48 ms 47224 KB Output is correct
7 Correct 42 ms 47224 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 48752 KB Output is correct
2 Correct 54 ms 48828 KB Output is correct
3 Correct 55 ms 48752 KB Output is correct
4 Correct 56 ms 48752 KB Output is correct
5 Correct 74 ms 48740 KB Output is correct
6 Correct 51 ms 47864 KB Output is correct
7 Correct 59 ms 48164 KB Output is correct
8 Correct 66 ms 48376 KB Output is correct
9 Correct 48 ms 47736 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 47352 KB Output is correct
2 Correct 43 ms 47392 KB Output is correct
3 Correct 42 ms 47352 KB Output is correct
4 Correct 44 ms 47324 KB Output is correct
5 Correct 43 ms 47352 KB Output is correct
6 Correct 42 ms 47352 KB Output is correct
7 Correct 41 ms 47332 KB Output is correct
8 Correct 41 ms 47324 KB Output is correct
9 Correct 41 ms 47352 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 48880 KB Output is correct
2 Correct 121 ms 48880 KB Output is correct
3 Correct 109 ms 48244 KB Output is correct
4 Correct 44 ms 47352 KB Output is correct
5 Correct 41 ms 47228 KB Output is correct
6 Correct 41 ms 47312 KB Output is correct
7 Correct 41 ms 47432 KB Output is correct
8 Correct 259 ms 49520 KB Output is correct
9 Correct 259 ms 49484 KB Output is correct