oj.uz

Submission #102431

# Submission time Handle Problem Language Result Execution time Memory
102431 2019-03-25T01:58:13 Z eriksuenderhauf Holiday (IOI14_holiday) C++11
100 / 100
 2792 ms 16008 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];
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;
	int nx = oL;
	indL[m] = oL;
	for (int i = oL; i >= oR; i--) {
		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;
			nx = i;
		}
	}
	for (int i = nx; i >= oR; i--)
		upd(0, n - 1, 1, rev[i], 0);
	dfsL(m + 1, r, nx, oR, st);
	for (int i = oL; i >= oR; i--)
		upd(0, n - 1, 1, rev[i], 0);
	dfsL(l, m - 1, oL, nx, st);
	/*for (int i = oL; i >= oR; i--)
		upd(0, n - 1, 1, rev[i], 0);
	dfsL(l, m - 1, oL, nx, st);
	for (int i = oL; i > nx; i--)
		upd(0, n - 1, 1, rev[i], 1);
	dfsL(m + 1, r, nx, oR, st);
	for (int i = nx; i >= oR; i--)
		upd(0, n - 1, 1, rev[i], 1);*/
}

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;
	int nx = oL;
	indR[m] = oL;
	for (int i = oL; i <= oR; i++) {
		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;
			nx = i;
		}
	}
	for (int i = nx; i <= oR; i++)
		upd(0, n - 1, 1, rev[i], 0);
	dfsR(m + 1, r, nx, oR, st);
	for (int i = oL; i <= oR; i++)
		upd(0, n - 1, 1, rev[i], 0);
	dfsR(l, m - 1, oL, nx, st);
	/*for (int i = oL; i <= oR; i++)
		upd(0, n - 1, 1, rev[i], 0);
	dfsR(l, m - 1, oL, nx, st);
	for (int i = oL; i < nx; i++)
		upd(0, n - 1, 1, rev[i], 1);
	dfsR(m + 1, r, nx, oR, st);
	for (int i = nx; i <= oR; i++)
		upd(0, n - 1, 1, rev[i], 1);*/
}

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, [](ll l, ll r) {
		return arr[l] > arr[r];
	});
	sort(arr, arr + n, [](ll l, ll 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);
	}
	memset(vR, 0, sizeof vR);
	memset(vL, 0, sizeof vL);
	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

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 7 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5092 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1887 ms 15092 KB Output is correct
2 Correct 2189 ms 15096 KB Output is correct
3 Correct 1947 ms 15012 KB Output is correct
4 Correct 2215 ms 15140 KB Output is correct
5 Correct 2739 ms 13816 KB Output is correct
6 Correct 827 ms 9780 KB Output is correct
7 Correct 1249 ms 9976 KB Output is correct
8 Correct 1594 ms 10232 KB Output is correct
9 Correct 627 ms 10360 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 5368 KB Output is correct
2 Correct 36 ms 5480 KB Output is correct
3 Correct 38 ms 5496 KB Output is correct
4 Correct 43 ms 5368 KB Output is correct
5 Correct 33 ms 5240 KB Output is correct
6 Correct 18 ms 5120 KB Output is correct
7 Correct 14 ms 5120 KB Output is correct
8 Correct 14 ms 5120 KB Output is correct
9 Correct 15 ms 5248 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2049 ms 16008 KB Output is correct
2 Correct 2063 ms 16008 KB Output is correct
3 Correct 1056 ms 8568 KB Output is correct
4 Correct 36 ms 5248 KB Output is correct
5 Correct 14 ms 5168 KB Output is correct
6 Correct 16 ms 5120 KB Output is correct
7 Correct 14 ms 5120 KB Output is correct
8 Correct 2792 ms 12780 KB Output is correct
9 Correct 2782 ms 12976 KB Output is correct