Submission #78975

#	Time	Username	Problem	Language	Result	Execution time	Memory
78975		tmwilliamlin168	Holiday (IOI14_holiday)	C++14	100 / 100	760 ms	8436 KiB

holiday

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

#define ll long long

const int mxN=1e5;
int n, s, d, *a, p[mxN], b[mxN], cl;
ll ans, c1[2*mxN+mxN/2+1], c2[2*mxN+mxN/2+1];
array<ll, 2> ft[mxN+1];
vector<int> v;

void upd(int i, array<ll, 2> x) {
	for(++i; i<=n; i+=i&-i) {
		ft[i][0]+=x[0];
		ft[i][1]+=x[1];
	}
}

void ml(int nl) {
	while(cl<nl) {
		++cl;
		if(v[cl]!=-1)
			upd(b[v[cl]], {1, a[v[cl]]});
	}
	while(cl>nl) {
		if(v[cl]!=-1)
			upd(b[v[cl]], {-1, -a[v[cl]]});
		--cl;
	}
}

void s3(int l1, int r1, int l2, int r2, ll c[2*mxN+mxN/2+1]) {
	if(l1>r1)
		return;
	int m1=(l1+r1)/2;
	array<ll, 2> m2{-1};
	for(int i=l2; i<=r2; ++i) {
		ml(i);
		ll s2=0;
		for(int j=16, lb=0, s1=0; j>=0; --j) {
			if(lb+(1<<j)<=n&&s1+ft[lb+(1<<j)][0]<=m1-i) {
				lb+=1<<j;
				s1+=ft[lb][0];
				s2+=ft[lb][1];
			}
		}
		m2=max(array<ll, 2>{s2, -i}, m2);
	}
	c[m1]=m2[0];
	s3(l1, m1-1, l2, -m2[1], c);
	s3(m1+1, r1, -m2[1], r2, c);
}

void s2(ll c[2*mxN+mxN/2+1]) {
	memset(ft, 0, sizeof(ft));
	cl=-1;
	s3(0, d, 0, v.size()-1, c);
	v.clear();
}

void s1() {
	sort(p, p+n, [&](const int &i, const int &j) {
		return a[i]>a[j];
	});
	for(int i=0; i<n; ++i)
		b[p[i]]=i;
	for(int i=s; i>=0; --i)
		v.push_back(i);
	s2(c1);
	v.push_back(-1);
	for(int i=s+1; i<n; ++i) {
		v.push_back(-1);
		v.push_back(i);
	}
	s2(c2);
	for(int i=0; i<=d; ++i)
		ans=max(c1[i]+c2[d-i], ans);
}

ll findMaxAttraction(int n2, int s2, int d2, int a2[]) {
	n=n2;
	s=s2;
	d=d2;
	a=a2;
	for(int i=0; i<n; ++i)
		p[i]=i;
	s1();
	s=n-1-s;
	for(int i=0; i<n-1-i; ++i)
		swap(a[i], a[n-1-i]);
	s1();
    return ans;
}

Compilation message (stderr)

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