Submission #211770

#	Time	Username	Problem	Language	Result	Execution time	Memory
211770		cgiosy	Holiday (IOI14_holiday)	C++17	23 / 100	164 ms	43772 KiB

holiday

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

struct pst {
	struct T { ll x; int cnt, l, r; };
	int N, id=1, td=0;
	vector<T> A;
	vector<int> D, X;
	pst(vector<int>&& _): N(_.size()), A(1800000), D(N+1), X(move(_)) {}
	void add(int x, int s, int e, int&i) {
		int p=i; i=++id;
		A[i]={A[p].x+X[x], A[p].cnt+1, A[p].l, A[p].r};
		if(s==e) return;
		int m=s+e>>1;
		if(x<=m) add(x, s, m, A[i].l);
		else add(x, m+1, e, A[i].r);
	}
	void add(int x) { td++; add(x, 0, N-1, D[td]=D[td-1]); }
	ll sum(int k, int s, int e, int i, int j) {
		if(s==e) return ll(X[s])*min(k, A[j].cnt-A[i].cnt);
		int m=s+e>>1, n=A[A[j].r].cnt-A[A[i].r].cnt;
		if(k<=n) return sum(k, m+1, e, A[i].r, A[j].r);
		else return sum(k-n, s, m, A[i].l, A[j].l)+A[A[j].r].x-A[A[i].r].x;
	}
	ll sum(int l, int r, int k) {
		return sum(k, 0, N-1, D[l-1], D[r]);
	}
};
ll findMaxAttraction(int N, int st, int M, int A[]) {
	vector<int> X(A, A+N);
	sort(begin(X), end(X));
	for(int i=0; i<N; i++) A[i]=lower_bound(begin(X), end(X), A[i])-begin(X);
	pst t(move(X));
	for(int i=0; i<N; i++) t.add(A[i]); ++st;
	function<ll(int, int, int, int)> f=
	[&](int s, int e, int l, int r) {
		if(l>r || s>e) return ll(0);
		int m=s+e>>1;
		pair<ll, int> n={-1, -1};
		for(int i=l; i<=r; i++)
			n=max(n, {t.sum(m, i, M+m-i-min(i-st, st-m)), i});
		return max({n.first, f(s, m-1, l, n.second), f(m+1, e, n.second, r)});
	};
	return f(1, st, st, N);
}

Compilation message (stderr)

holiday.cpp: In member function 'void pst::add(int, int, int, int&)':
holiday.cpp:16:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~
holiday.cpp: In member function 'll pst::sum(int, int, int, int, int)':
holiday.cpp:23:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1, n=A[A[j].r].cnt-A[A[i].r].cnt;
         ~^~
holiday.cpp: In function 'll findMaxAttraction(int, int, int, int*)':
holiday.cpp:36:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=0; i<N; i++) t.add(A[i]); ++st;
  ^~~
holiday.cpp:36:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=0; i<N; i++) t.add(A[i]); ++st;
                                      ^~
holiday.cpp: In lambda function:
holiday.cpp:40:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m=s+e>>1;
         ~^~

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