Submission #448246

#	Time	Username	Problem	Language	Result	Execution time	Memory
448246		naman1601	Holiday (IOI14_holiday)	C++17	100 / 100	837 ms	8908 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;

typedef long long big;
typedef long double ludo;
#define pbb pair<big, big>
#define pii pair<int, int>
#define fe first
#define se second
#define maxheap priority_queue
#define mset multiset
#define uset unordered_set
#define umap unordered_map
#define fr(i, s, e) for(int i = s; i < e; i++)
#define revfr(i, s, e) for(int i = s - 1; i >= e; i--)
#define getv(v, n) for(int i = 0; i < n; i++) cin >> v[i];
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug(text) if(do_debug) {cout << (#text) << ": " << text << endl;}
#define nl "\n"

// making some things easily accessible
// push_back pop_back emplace_back make_pair lower_bound upper_bound reserve resize reverse

const big mod = 1000000007;
// const big mod = 998244353;
const big infinity = 1000000000000000000;
const int inf = 1e9 + 5;
bool do_debug = false;


struct segt {

	int tl;
	vector<big> t;

	void init(int l, big val) {

		tl = l;
		t = vector<big>(tl << 2, val);
	}

	big task(big child1, big child2) {
	
		return child1 + child2;
	}
	
	void update(int node, int l, int r, int pos, big val) {
	
		if(l == r) {
	
			t[node] = val;
	
		} else {
	
			int mid = (l + r) >> 1;
	
			if(pos <= mid) {
	
				update(node << 1, l, mid, pos, val);
	
			} else {
	
				update((node << 1) + 1, mid + 1, r, pos, val);
			}
	
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void update(int pos, big val) {

		update(1, 0, tl - 1, pos, val);
	}
	
	big query(int node, int l, int r, int lq, int rq) {
	
		if(lq > rq) {
	
			return 0;
	
		} else if(lq <= l && rq >= r) {
	
			return t[node];
	
		} else {
	
			int mid = (l + r) >> 1;
			return task(query(node << 1, l, mid, lq, min(rq, mid)), query((node << 1) + 1, mid + 1, r, max(lq, mid + 1), rq));
		}
	}

	big query(int lq, int rq) {

		return query(1, 0, tl - 1, lq, rq);
	}
	
	void build(vector<pii>& v, int node, int l, int r) {
	
		if(l == r) {
	
			t[node] = v[l].fe;
	
		} else {
	
			int mid = (l + r) >> 1;
			build(v, node << 1, l, mid);
			build(v, (node << 1) + 1, mid + 1, r);
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void build(vector<pii>& v) {

		build(v, 1, 0, tl - 1);
	}
};


struct countt {

	int tl;
	vector<int> t;

	void init(int l, int val) {

		tl = l;
		t = vector<int>(tl << 2, val);
	}

	int task(int child1, int child2) {
	
		return child1 + child2;
	}
	
	void update(int node, int l, int r, int pos, int val) {
	
		if(l == r) {
	
			t[node] = val;
	
		} else {
	
			int mid = (l + r) >> 1;
	
			if(pos <= mid) {
	
				update(node << 1, l, mid, pos, val);
	
			} else {
	
				update((node << 1) + 1, mid + 1, r, pos, val);
			}
	
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void update(int pos, int val) {

		update(1, 0, tl - 1, pos, val);
	}
	
	int query(int node, int l, int r, int v) {
	
		if(l == r) {

			return l;

		} else {

			int mid = ((l + r) >> 1);

			if(t[node << 1] >= v) {

				return query(node << 1, l, mid, v);

			} else {

				return query((node << 1) + 1, mid + 1, r, v - t[node << 1]);
			}
		}
	}

	int query(int v) {

		return query(1, 0, tl - 1, v);
	}
	
	void build(vector<int>& v, int node, int l, int r) {
	
		if(l == r) {
	
			t[node] = v[l];
	
		} else {
	
			int mid = (l + r) >> 1;
			build(v, node << 1, l, mid);
			build(v, (node << 1) + 1, mid + 1, r);
			t[node] = task(t[node << 1], t[(node << 1) + 1]);
		}
	}

	void build(vector<int>& v) {

		build(v, 1, 0, tl - 1);
	}
};


int n, d, sp;
vector<int> rmap;
vector<big> dp;
segt st;
countt ct;
vector<big> vals;
int L, R;

void cf(int l, int r) {

	while(R < r) {

		R++;
		ct.update(rmap[R], 1);
		st.update(rmap[R], vals[rmap[R]]);
	}

	while(L > l) {

		L--;
		ct.update(rmap[L], 1);
		st.update(rmap[L], vals[rmap[L]]);
	}

	while(L < l) {

		ct.update(rmap[L], 0);
		st.update(rmap[L], 0);
		L++;
	}

	while(R > r) {

		ct.update(rmap[R], 0);
		st.update(rmap[R], 0);
		R--;
	}
}


void f(int l, int r, int o_l, int o_r) {

	if(l > r) {

		return;
	}

	int mid = ((r - l) >> 1) + l;
	big ans = -1;
	int o = 0;

	fr(i, o_l, o_r + 1) {

		cf(i, mid);
		int len = mid - i + 1;
		int dist = mid - i + min(mid - sp, sp - i);
		int rem = d - dist;

		if(rem > len) {

			rem = len;
		}

		big temp = st.query(0, ct.query(rem));

		if(temp > ans) {

			ans = temp;
			o = i;
		}
	}

	dp[mid] = ans;
	f(l, mid - 1, o_l, o);
	f(mid + 1, r, o, o_r);
}


big findMaxAttraction(int N, int start, int D, int attraction[5]) {

	n = N;
	sp = start;
	d = D;
	rmap.resize(n, 0);
	dp.resize(n, -1);
	vals.resize(n, 0);

	vector<pii> aux(n);

	fr(i, 0, n) {

		aux[i] = make_pair(attraction[i], i);
	}

	sort(aux.begin(), aux.end());
	reverse(aux.begin(), aux.end());

	fr(i, 0, n) {

		vals[i] = aux[i].fe;
		rmap[aux[i].se] = i;
	}

	st.init(n, 0);
	ct.init(n, 0);

	L = sp;
	R = sp;
	ct.update(rmap[sp], 1);
	st.update(rmap[sp], vals[rmap[sp]]);

	f(sp, n - 1, 0, sp);

	big ans = -1;

	fr(i, 0, n) {

		ans = max(ans, dp[i]);
	}

	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53