oj.uz

답안 #134230

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134230 2019-07-22T08:40:41 Z antimirage 휴가 (IOI14_holiday) C++14
100 / 100
 2829 ms 52192 KB 
#include"holiday.h"
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;
 
const int N = 1e5 + 3;
 
long long d1[2][(int)3e5], d2[2][(int)3e5];
 
struct tree{
	int cnt, l, r;
	long long sum;
} 
t[N * 19];
 
int n, a[N], sz, st, root[N], D;
 
vector <int> vec;
 
void update (int ov, int nv, int pos, int val, int tl = 0, int tr = n) {
	if (tl == tr) {
		t[nv].cnt = t[ov].cnt + 1; 
		t[nv].sum = t[ov].sum + val;
	} else {
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			t[nv].r = t[ov].r;
			t[nv].l = ++sz;
			update( t[ov].l, t[nv].l, pos, val, tl, tm );
		} else {
			t[nv].l = t[ov].l;
			t[nv].r = ++sz;
			update( t[ov].r, t[nv].r, pos, val, tm + 1, tr );
		}
		t[nv].cnt = t[ t[nv].l ].cnt + t[ t[nv].r ].cnt;
		t[nv].sum = t[ t[nv].l ].sum + t[ t[nv].r ].sum;
	}
}
long long get (int ov, int nv, int k, int tl = 0, int tr = n) {
	if (tl == tr) {
		return min((t[nv].sum - t[ov].sum), k * 1ll * vec[tl]);
	}
	int tm = (tl + tr) >> 1;
	
	if (t[t[nv].r].cnt - t[t[ov].r].cnt >= k) {
		return get(t[ov].r, t[nv].r, k, tm + 1, tr);
	}
	return get(t[ov].l, t[nv].l, k - (t[t[nv].r].cnt - t[t[ov].r].cnt), tl, tm ) + t[t[nv].r].sum - t[t[ov].r].sum;
}
 
void solve1 (int opl, int opr, int dl, int dr) {
	if (dl > dr) return;
	int dm = (dl + dr) >> 1, opt;
	long long res = 0, val;
	
	for (int i = opl; i <= opr; i++) {
		if ( dm - (i - st) <= 0 ) break;
		val = get(root[st - 1], root[i], dm - (i - st));
		if ( val > res ) {
			res = val;
			opt = i;
		}
	}
	d1[0][dm] = res;
	if (dm + (opt - st) <= D) d1[1][dm + (opt - st)] = res;
	solve1(opl, opt, dl, dm - 1);
	solve1(opt, opr, dm + 1, dr);
}
void solve2 (int opl, int opr, int dl, int dr) {
	if (dl > dr || opl > opr) return;
	int dm = (dl + dr) >> 1, opt;
	long long res = 0, val;
	
	for (int i = opr; i >= opl; i--) {
		if ( dm - (st - i) <= 0 ) break;
		val = get(root[i - 1], root[st - 1], dm - (st - i));
		if ( val > res ) {
			res = val;
			opt = i;
		}
	}
	d2[0][dm] = res;
	if (dm + (st - opt) <= D) d2[1][dm + (st - opt)] = res;
	solve2(opl, opt, dm + 1, dr);
	solve2(opt, opr, dl, dm - 1);
}
long long findMaxAttraction(int A, int start, int ASD, int at[]) { start++; D = ASD;
	n = A;
	st = start;
	
	for (int i = 0; i < n; i++) {
		vec.pb(at[i]);
	}
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for (int i = 0; i < n; i++) {
		a[i + 1] = lower_bound(all(vec), at[i]) - vec.begin();
		root[i + 1] = ++sz;
		update( root[i], root[i + 1], a[i + 1], vec[ a[i + 1] ] );
	}
	
	solve1(start, n, 1, min(D, 2 * (n - start) + 1) );
	solve2(1, start - 1, 1, min(D, 2 * (start - 1) + 1) );
	
	for (int i = 1; i <= D; i++) {
		d1[0][i] = max(d1[0][i - 1], d1[0][i]);
		d1[1][i] = max(d1[1][i - 1], d1[1][i]);
		d2[0][i] = max(d2[0][i - 1], d2[0][i]);
		d2[1][i] = max(d2[1][i - 1], d2[1][i]);
	}
	
	long long ans = 0;
	for (int i = 0; i <= D; i++) {
		ans = max(ans, d1[1][i] + d2[0][D - i]);
		ans = max(ans, d1[0][i] + d2[1][D - i]);
	}
	return ans;
}

Compilation message

holiday.cpp: In function 'void solve1(int, int, int, int)':
holiday.cpp:71:16: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (dm + (opt - st) <= D) d1[1][dm + (opt - st)] = res;
           ~~~~~^~~~~
holiday.cpp: In function 'void solve2(int, int, int, int)':
holiday.cpp:89:15: warning: 'opt' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if (dm + (st - opt) <= D) d2[1][dm + (st - opt)] = res;
           ~~~~^~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 283 ms 50584 KB Output is correct
2 Correct 2829 ms 50724 KB Output is correct
3 Correct 283 ms 50928 KB Output is correct
4 Correct 304 ms 50800 KB Output is correct
5 Correct 224 ms 44144 KB Output is correct
6 Correct 74 ms 17248 KB Output is correct
7 Correct 124 ms 24264 KB Output is correct
8 Correct 142 ms 28888 KB Output is correct
9 Correct 52 ms 15480 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 1528 KB Output is correct
2 Correct 7 ms 1528 KB Output is correct
3 Correct 8 ms 1528 KB Output is correct
4 Correct 9 ms 1400 KB Output is correct
5 Correct 7 ms 1276 KB Output is correct
6 Correct 3 ms 636 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 3 ms 632 KB Output is correct
9 Correct 3 ms 608 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 52192 KB Output is correct
2 Correct 422 ms 51520 KB Output is correct
3 Correct 101 ms 18932 KB Output is correct
4 Correct 7 ms 1272 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 452 ms 45160 KB Output is correct
9 Correct 478 ms 45252 KB Output is correct