Submission #370776

#	Time	Username	Problem	Language	Result	Execution time	Memory
370776		NachoLibre	Holiday (IOI14_holiday)	C++17	100 / 100	1987 ms	14952 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
#include "holiday.h"
#else
#endif

struct ovo {
	ovo() {
		l = r = NULL;
		c = 0;
		x = 0;
	}
	ovo *l, *r;
	int c;
	ll x;
	void P() {
		if(!l) l = new ovo();
		if(!r) r = new ovo();
		x = l->x + r->x;
		c = l->c + r->c;
	}
	void C(int a) {
		if(a == 0) x = c = 0;
		else x = a, c = 1;
	}
};

struct spt {
	spt() { }
	void init(int _n) {
		n = _n;
		rt = NULL;
	}
private:
	int n;
	ovo *rt;
	//  //  //  //
	static void Ci(int l, int r, ovo *&t, int vl, int si) {
		if(!t) t = new ovo();
		if(l == r) return t->C(vl);
		int m = l + r >> 1;
		if(m >= si) Ci(l, m, t->l, vl, si);
		else    Ci(1 + m, r, t->r, vl, si);
		t->P();
	}
	//  //  //  //
	static ll Xi(int l, int r, ovo *&t, int x) {
		if(!t) return 0ll;
		if(x >= t->c) return t->x;
		int lc = (t->l ? t->l->c : 0);
		ll lx = (t->l ? t->l->x : 0ll);
		int m = l + r >> 1;
		if(lc >= x) return Xi(l, m, t->l, x);
		else return lx + Xi(1 + m, r, t->r, x - lc);
	}
public:
	//  //  //  //
	void C(int si, int vl) {
		Ci(0, n - 1, rt, vl, si);
	}
	//  //  //  //
	void R(int si) {
		C(si, 0);
	}
	//  //  //  //
	ll X(int x) {
		return Xi(0, n - 1, rt, x);
	}
} st;

const int N = 100005, D = N * 3;
int si[N], rw[N];
ll rv[2][2][D];
int sm, ub;

void DCC(int ld, int rd, int li, int ri) {
	if(ld > rd || li > ri) return;
	int md = ld + rd >> 1;
	ll ap = 0;
	int pi = li;
	for(int i = li; i <= ri; ++i) {
		int j = si[i];
		st.C(j, rw[j]);
		ll tp = 0;
		int ds = i + 1;
		if(ub) ds *= 2;
		if(md - ds > 0) tp = st.X(md - ds);
		if(tp > ap) {
			ap = tp;
			pi = i;
		}
	}
	rv[sm][ub][md] = ap;
	for(int i = ri; i >= pi; --i) {
		st.R(si[i]);
	}
	DCC(md + 1, rd, pi, ri);
	for(int i = pi - 1; i >= li; --i) {
		st.R(si[i]);
	}
	DCC(ld, md - 1, li, pi);
}

ll findMaxAttraction(int n, int s, int d, int *a) {
	st.init(n);
	{
		vector<pair<int, int>> v;
		for(int i = s + 1; i < n; ++i) {
			v.push_back({a[i], i - s - 1});
		}
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		for(int i = 0; i < n - s - 1; ++i) {
			si[v[i].second] = i;
			rw[i] = v[i].first;
		}
	}
	sm = 0;
	ub = 0;
	if(n - s > 1) DCC(0, d, 0, n - s - 2);
	ub = 1;
	if(n - s > 1) DCC(0, d, 0, n - s - 2);
	{
		vector<pair<int, int>> v;
		for(int i = 0; i < s; ++i) {
			v.push_back({a[i], s - i - 1});
		}
		sort(v.begin(), v.end());
		reverse(v.begin(), v.end());
		for(int i = 0; i < s; ++i) {
			si[v[i].second] = i;
			rw[i] = v[i].first;
		}
	}
	sm = 1;
	ub = 0;
	if(s) DCC(0, d, 0, s - 1);
	ub = 1;
	if(s) DCC(0, d, 0, s - 1);
	ll dr = 0;
	for(int i = 0; i <= d; ++i) {
		dr = max(dr, rv[0][1][i] + rv[1][0][d - i]);
		if(i ^ d) dr = max(dr, rv[0][1][i] + rv[1][0][d - i - 1] + a[s]);
		//  //  //  //
		dr = max(dr, rv[1][1][i] + rv[0][0][d - i]);
		if(i ^ d) dr = max(dr, rv[1][1][i] + rv[0][0][d - i - 1] + a[s]);
	}
	#ifdef wambule
	for(int i = 0; i < 2; ++i) {
		for(int j = 0; j < 2; ++j) {
			for(int k = 0; k <= d; ++k) {
				cout << "[] " << i << " " << j << " " << k << " " << rv[i][j][k] << endl;
			}
		}
	}
	#endif
	return dr;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tc = 2;
	if(tc == 1) {
		int n = 5;
		int s = 2;
		int d = 7;
		int a[] = {10, 2, 20, 30, 1};
		ll fp = findMaxAttraction(n, s, d, a);
		cout << fp << endl;
	} else if(tc == 2) {
		int n = 5;
		int s = 0;
		int d = 7;
		int a[] = {2, 1, 100, 1, 2};
		ll fp = findMaxAttraction(n, s, d, a);
		cout << fp << endl;
	}
	return 0;
}
#endif

Compilation message (stderr)

holiday.cpp: In static member function 'static void spt::Ci(int, int, ovo*&, int, int)':
holiday.cpp:46:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |   int m = l + r >> 1;
      |           ~~^~~
holiday.cpp: In static member function 'static ll spt::Xi(int, int, ovo*&, int)':
holiday.cpp:57:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int m = l + r >> 1;
      |           ~~^~~
holiday.cpp: In function 'void DCC(int, int, int, int)':
holiday.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |  int md = ld + rd >> 1;
      |           ~~~^~~~

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