Submission #348800

#	Time	Username	Problem	Language	Result	Execution time	Memory
348800		dennisstar	Holiday (IOI14_holiday)	C++17	100 / 100	1780 ms	7020 KiB

holiday

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

using namespace std;
using ll = long long;

const int MX = 1e5 + 5;

int N, S, D;
ll H[MX], A;

struct myset {
	multiset<ll> S1, S2;
	ll V; int s, e;
	void init() {
		s=0; e=-1; V=0;
		S1.clear(); S2.clear();
	}
	void ins(int i) {
		if (S1.empty()||*S1.rbegin()<H[i]) S2.em(H[i]), V+=H[i];
		else S1.em(H[i]);
	}
	void er(int i) {
		if (S1.find(H[i])!=S1.end()) S1.erase(S1.find(H[i]));
		else if (S2.find(H[i])!=S2.end()) S2.erase(S2.find(H[i])), V-=H[i];
		else assert(false);
	}
	void res(int ss, int ee) {
		for (int i=s-1; i>=ss; i--) ins(i);
		for (int i=e+1; i<=ee; i++) ins(i);
		for (int i=s; i<ss; i++) er(i);
		for (int i=e; i>ee; i--) er(i);
		s=ss; e=ee;
	}
	ll get(int c) {
		if (c<=0) return 0;
		while (S2.size()<c&&S1.size()>0) V+=*S1.rbegin(), S2.em(*S1.rbegin()), S1.erase(--S1.end());
		while (S2.size()>c) V-=*S2.begin(), S1.em(*S2.begin()), S2.erase(S2.begin());
		return V;
	}
}MS;

void sol(int s, int e, int ss, int ee) {
	if (s>e||ss>ee) return ;
	int m=(s+e)/2, mi=ss; ll mx=0;
	for (int i=ss; i<=ee; i++) {
		MS.res(m, i);
		ll r=MS.get(D-(S+i-2*m));
		if (r>mx) mx=r, mi=i;
	}
	A=max(A, mx);
	if (s==e) return ;
	sol(s, m-1, ss, mi); sol(m+1, e, mi, ee);
}

ll findMaxAttraction(int n, int s, int d, int h[]) {
	N=n, S=s, D=d;
	for (int i=0; i<N; i++) H[i]=h[i];
	MS.init();
	sol(0, S, S+1, N-1);
	reverse(H, H+N); S=N-1-S; MS.init();
	sol(0, S, S+1, N-1);
	return A;
}

Compilation message (stderr)

holiday.cpp: In member function 'll myset::get(int)':
holiday.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   while (S2.size()<c&&S1.size()>0) V+=*S1.rbegin(), S2.em(*S1.rbegin()), S1.erase(--S1.end());
      |          ~~~~~~~~~^~
holiday.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   while (S2.size()>c) V-=*S2.begin(), S1.em(*S2.begin()), S2.erase(S2.begin());
      |          ~~~~~~~~~^~

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