oj.uz

답안 #586717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
586717 2022-06-30T14:54:22 Z SeDunion 휴가 (IOI14_holiday) C++17
100 / 100
 890 ms 4948 KB 
#include"holiday.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
 
using namespace std;
using ll = long long;
 
const int N = 1e5 + 123;

int n;

pair<int,int>pp[N];

int cnt[N << 2];
ll sum[N << 2];

void upd(int pos, int type, int l = 0, int r = n, int v = 1) {
	if (r - l == 1) {
		cnt[v] += type, sum[v] += type * pp[l].first;
		return;
	}
	int m = (l + r) >> 1;
	if (pos < m) upd(pos, type, l, m, v << 1);
	else upd(pos, type, m, r, v<<1|1);
	cnt[v] = cnt[v << 1] + cnt[v<<1|1];
	sum[v] = sum[v << 1] + sum[v<<1|1];
}

ll get(int y, int l = 0, int r = n, int v = 1) {
	if (r - l == 1) return y ? sum[v] : 0;
	int m = (l + r) >> 1;
	if (cnt[v<<1|1] >= y) return get(y, m, r, v<<1|1);
	else return get(y - cnt[v<<1|1], l, m, v << 1) + sum[v<<1|1];
}

int pos[N];

ll ans;

int start, d;

int L = 1, R = 0;

void moveL(int s) {
	while (L < s) {
		upd(pos[L++], -1);
	}
	while (L > s) {
		upd(pos[--L], +1);
	}
}

void moveR(int s) {
	while (R < s) {
		upd(pos[++R], +1);
	}
	while (R > s) {
		upd(pos[R--], -1);
	}
}

void solve(int l, int r, int opl, int opr) {
	if (l > r) return;
	int m = (l + r) >> 1;
	int opm = -1;
	moveL(m);
	int x = d - (start - m);
	ll cur = 0;
	opm = opl;
	for (int i = opl ; i <= opr ; ++ i) {
		moveR(i);
		int y = x - (i - m);
		if (y > 0) {
			ll temp = get(y);
			if (temp > cur) {
				opm = i;
				cur = temp;
			}
		}
	}
	ans = max(ans, cur);
	solve(l, m - 1, opl, opm);
	solve(m + 1, r, opm, opr);
}

ll findMaxAttraction(int n_, int start_, int d_, int attraction[]) {
	n = n_, start = start_, d = d_;
	for (int i = 0 ; i < n ; ++ i) {
		pp[i] = {attraction[i], i};
	}
	sort(pp, pp + n);
	for (int i = 0 ; i < n ; ++ i) {
		pos[pp[i].second] = i;
	}
	for (int _ = 0 ; _ < 2 ; ++ _) {
		solve(0, start, start, n - 1);
		moveL(1);
		moveR(0);
		for (int i = 0 ; i < n ; ++ i) {
			pp[i].second = n - pp[i].second - 1;
			pos[pp[i].second] = i;
		}
		reverse(attraction, attraction + n);
		start = n - start - 1;
	}
	return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 157 ms 4936 KB Output is correct
2 Correct 150 ms 4936 KB Output is correct
3 Correct 147 ms 4844 KB Output is correct
4 Correct 148 ms 4948 KB Output is correct
5 Correct 202 ms 4808 KB Output is correct
6 Correct 56 ms 1748 KB Output is correct
7 Correct 109 ms 2828 KB Output is correct
8 Correct 149 ms 2952 KB Output is correct
9 Correct 36 ms 1688 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 4936 KB Output is correct
2 Correct 152 ms 4932 KB Output is correct
3 Correct 351 ms 2772 KB Output is correct
4 Correct 11 ms 840 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 3 ms 724 KB Output is correct
8 Correct 831 ms 4932 KB Output is correct
9 Correct 890 ms 4936 KB Output is correct