oj.uz

답안 #102439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102439 2019-03-25T02:19:47 Z eriksuenderhauf 휴가 (IOI14_holiday) C++11
100 / 100
 3111 ms 15144 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "holiday.h"
//#include "grader.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef cc_hash_table<int,int,hash<int>> ht;
const double pi = acos(-1);
const int MOD = 1e9 + 9;
const int INF = 1e9 + 7;
const int MAXN = 3e5 + 5;
const double eps = 1e-9;
struct node
{
	ll sum; int act;
} seg[MAXN*4];
ll arr[MAXN], ind[MAXN], rev[MAXN];
ll indR[MAXN], indL[MAXN];
ll vR[MAXN], vL[MAXN];
int n;

node operator +(node &lhs, const node &rhs) {
	return {lhs.sum + rhs.sum, lhs.act + rhs.act};
}

node operator +=(node &lhs, const node &rhs) {
	return lhs = lhs + rhs;
}

void build(int l, int r, int k) {
	if (l == r) {
		seg[k] = {0, 0};
		return;
	}
	int m = (l + r) / 2;
	build(l, m, k*2);
	build(m+1, r, k*2+1);
	seg[k] = seg[k*2] + seg[k*2+1];
}

void upd(int l, int r, int k, int a, int v) {
	if (r < a || a < l) return;
	if (a <= l && r <= a) {
		seg[k].act = v;
		if (seg[k].act == 1)
			seg[k].sum = arr[l];
		else
			seg[k].sum = 0;
		return;
	}
	int m = (l + r) / 2;
	upd(l, m, k*2, a, v);
	upd(m+1, r, k*2+1, a, v);
	seg[k] = seg[k*2] + seg[k*2+1];
}

node qry(int l, int r, int k, int cnt) {
	if (seg[k].act == 0) return {0, 0};
	if (seg[k].act <= cnt) return seg[k];
	int m = (l + r) / 2;
	node lhs = qry(l, m, k*2, cnt);
	if (lhs.act >= cnt) return lhs;
	return lhs + qry(m + 1, r, k*2+1, cnt - lhs.act);
}

void dfsL(int l, int r, int oL, int oR, int st) {
	if (l > r || oR < 0 || oL < 0) return;
	int m = (l + r) / 2;
	indL[m] = oL;
	vL[m] = 0;
	for (int i = oL; i >= oR; i--) {
		if (m - (st - i) < 0) break;
		upd(0, n - 1, 1, rev[i], 1);
		ll val = qry(0, n - 1, 1, m - (st - i)).sum;
		if (val > vL[m]) {
			vL[m] = val;
			indL[m] = i;
		}
	}
	for (int i = indL[m]; i >= oR; i--) upd(0, n - 1, 1, rev[i], 0);
	dfsL(m + 1, r, indL[m], oR, st);
	for (int i = oL; i >= oR; i--) upd(0, n - 1, 1, rev[i], 0);
	dfsL(l, m - 1, oL, indL[m], st);
}

void dfsR(int l, int r, int oL, int oR, int st) {
	if (l > r || oL >= n || oR >= n) return;
	int m = (l + r) / 2;
	indR[m] = oL;
	vR[m] = 0;
	for (int i = oL; i <= oR; i++) {
		if (m - (i - st) < 0) break;
		upd(0, n - 1, 1, rev[i], 1);
		ll val = qry(0, n - 1, 1, m - (i - st)).sum;
		if (val > vR[m]) {
			vR[m] = val;
			indR[m] = i;
		}
	}
	for (int i = indR[m]; i <= oR; i++) upd(0, n - 1, 1, rev[i], 0);
	dfsR(m + 1, r, indR[m], oR, st);
	for (int i = oL; i <= oR; i++) upd(0, n - 1, 1, rev[i], 0);
	dfsR(l, m - 1, oL, indR[m], st);
}

ll findMaxAttraction(int N, int start, int d, int attraction[]) {
	n = N;
	for (int i = 0; i < n; i++) {
		ind[i] = i;
		arr[i] = attraction[i];
	}
	sort(ind, ind + n, [](int l, int r) {
		return arr[l] > arr[r];
	});
	sort(arr, arr + n, [](int l, int r) {
		return l > r;
	});
	for (int i = 0; i < n; i++)
		rev[ind[i]] = i;
	build(0, n - 1, 1);
	dfsR(1, d, start, n - 1, start);
	build(0, n - 1, 1);
	dfsL(1, d, start - 1, 0, start - 1);
	ll ans = 0;
	for (int i = 1; i <= d; i++) {
		ll tmp = vR[i];
		if (d - i - (indR[i] - start + 1) >= 0)
			tmp += vL[d - i - (indR[i] - start + 1)];
		ans = max(ans, tmp);
	}
	build(0, n - 1, 1);
	dfsR(1, d, start + 1, n - 1, start + 1);
	build(0, n - 1, 1);
	dfsL(1, d, start, 0, start);
	for (int i = 1; i <= d; i++) {
		ll tmp = vL[i];
		if (d - i - (start - indL[i] + 1) >= 0)
			tmp += vR[d - i - (start - indL[i] + 1)];
		ans = max(ans, tmp);
	}
	return ans;
}

Compilation message

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1808 ms 13512 KB Output is correct
2 Correct 2323 ms 13420 KB Output is correct
3 Correct 2081 ms 13504 KB Output is correct
4 Correct 2166 ms 13580 KB Output is correct
5 Correct 2989 ms 11300 KB Output is correct
6 Correct 866 ms 7908 KB Output is correct
7 Correct 1395 ms 6520 KB Output is correct
8 Correct 1724 ms 6932 KB Output is correct
9 Correct 629 ms 9348 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 916 KB Output is correct
2 Correct 33 ms 896 KB Output is correct
3 Correct 33 ms 888 KB Output is correct
4 Correct 33 ms 768 KB Output is correct
5 Correct 31 ms 768 KB Output is correct
6 Correct 12 ms 512 KB Output is correct
7 Correct 9 ms 384 KB Output is correct
8 Correct 10 ms 512 KB Output is correct
9 Correct 9 ms 512 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1884 ms 15100 KB Output is correct
2 Correct 2178 ms 15144 KB Output is correct
3 Correct 781 ms 4028 KB Output is correct
4 Correct 30 ms 640 KB Output is correct
5 Correct 9 ms 512 KB Output is correct
6 Correct 10 ms 512 KB Output is correct
7 Correct 12 ms 512 KB Output is correct
8 Correct 3111 ms 8936 KB Output is correct
9 Correct 2817 ms 8824 KB Output is correct