Submission #59222

#	Time	Username	Problem	Language	Result	Execution time	Memory
59222		Just_Solve_The_Problem	Holiday (IOI14_holiday)	C++17	100 / 100	1814 ms	18420 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define all(s) s.begin(), s.end()
#define sz(s) (int)s.size()

const int N = (int)1e5 + 7;

struct T {
	ll sum;
	int cnt;
	T() {
		sum = cnt = 0;
	}
};
int nn;

struct TT {
	T tree[N * 4];
	void upd(int pos, int val, int v = 1, int l = 0, int r = nn) {
		if (l == r) {
			if (val == -1) {
				tree[v].sum = 0;
				tree[v].cnt = 0;
			} else {
				tree[v].sum = val;
				tree[v].cnt = 1;
			}
			return ;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) {
			upd(pos, val, v + v, l, mid);
		} else {
			upd(pos, val, v + v + 1, mid + 1, r);
		}
		tree[v].sum = tree[v + v].sum + tree[v + v + 1].sum;
		tree[v].cnt = tree[v + v].cnt + tree[v + v + 1].cnt;
	}
	ll get(int take, int v = 1, int l = 0, int r = nn) {
		if (l == r) {
			if (take > 0) {
				return tree[v].sum;
			} else {
				return 0;
			}
		}
		int mid = (l + r) >> 1;
		if (tree[v + v + 1].cnt >= take) {
			return get(take, v + v + 1, mid + 1, r);
		} else {
			return get(take - tree[v + v + 1].cnt, v + v, l, mid) + tree[v + v + 1].sum;
		}
	}
};
TT tr;

vector < ll > a, b, A, B, a1, b1;
ll c[5][N * 3];

bool cmpa(int x, int y) {
	return A[x] < A[y];
}

bool cmpb(int x, int y) {
	return B[x] < B[y];
}

void divide(int id, int l, int r, int optl, int optr) {
	if (l > r) return ;
	int opt = optl;
	ll best = -1;
	int mid = (l + r) >> 1;
	for (int i = optl; i <= optr; i++) {
		if (id <= 2) {
			tr.upd(a1[i], A[i]);
		} else {
			tr.upd(b1[i], B[i]);
		}
		ll cost;
		if (id & 1 ^ 1) {
			cost = tr.get(mid - 2 * (i + 1));
		} else {
			cost = tr.get(mid - (i + 1));
		}
		if (cost > best) {
			best = cost;
			opt = i;
		}
	}
	if (id <= 2) {
		for (int i = opt; i <= optr; i++) {
			tr.upd(a1[i], -1);
		}
	} else {
		for (int i = opt; i <= optr; i++) {
			tr.upd(b1[i], -1);
		}
	}
	divide(id, mid + 1, r, opt, optr);
	
	if (id <= 2) {
		for (int i = optl; i <= opt; i++) {
			tr.upd(a1[i], -1);
		}
	} else {
		for (int i = optl; i <= opt; i++) {
			tr.upd(b1[i], -1);
		}
	}
	divide(id, l, mid - 1, optl, opt);
	c[id][mid] = max(best, c[id][mid]);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	nn = n;
	for (int i = 0; i < n; i++) {
		if (i < start) {
			A.pb(attraction[i]);
			a.pb(i);
		} else if (i > start) {
			B.pb(attraction[i]);
			b.pb(i - start - 1);
		}
	}
	reverse(all(A));
	sort(all(a), cmpa);
	sort(all(b), cmpb);
	a1.resize(n);
	b1.resize(n);
	for (int i = 0; i < sz(a); i++)
		a1[a[i]] = i;
	for (int i = 0; i < sz(b); i++)
		b1[b[i]] = i;
	if (!a.empty()) {
		divide(1, 1, d, 0, sz(a) - 1);
		divide(2, 1, d, 0, sz(a) - 1);
	}
	if (!b.empty()) {
		divide(3, 1, d, 0, sz(b) - 1);
		divide(4, 1, d, 0, sz(b) - 1);
	}
	ll ans = 0;
	for (int i = 0; i < d; i++) {
		ans = max(ans, c[2][i] + attraction[start] + c[3][d - i - 1]);
		ans = max(ans, c[1][d - i - 1] + attraction[start] + c[4][i]);
		ans = max(ans, c[2][i] + c[3][d - i]);
		ans = max(ans, c[1][d - i] + c[4][i]);
	}
	ans = max(ans, c[2][d] + c[3][0]);
	ans = max(ans, c[1][0] + c[4][d]);
	return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void divide(int, int, int, int, int)':
holiday.cpp:85:10: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   if (id & 1 ^ 1) {
       ~~~^~~
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 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53