Submission #519831

#	Time	Username	Problem	Language	Result	Execution time	Memory
519831		AdamGS	Holiday (IOI14_holiday)	C++17	100 / 100	1167 ms	37300 KiB

holiday

#include "holiday.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=4e5+7;
int ile[4*LIM], N;
pair<ll,ll>T[4*LIM], P[4*LIM];
ll sum[4*LIM], ans[4*LIM];
void upd1(int v, int x) {
	v+=N;
	while(v) {
		ile[v]+=x;
		v/=2;
	}
}
int znajdz(int k) {
	int v=1;
	while(v<N) {
		v*=2;
		if(ile[v]<k) {
			k-=ile[v];
			++v;
		}
	}
	return v-N;
}
void upd2(int v, ll x) {
	v+=N;
	while(v) {
		sum[v]+=x;
		v/=2;
	}
}
ll cnt(int l, int r) {
	l+=N; r+=N;
	ll x=sum[l];
	if(l!=r) x+=sum[r];
	while(l/2!=r/2) {
		if(l%2==0) x+=sum[l+1];
		if(r%2==1) x+=sum[r-1];
		l/=2; r/=2;
	}
	return x;
}
void dc(int l, int r, int a, int b, int n) {
	if(b<a) return;
	int mid=(a+b)/2;
	ll ma=0, gdzie=l;
	for(int i=l; i<=r; ++i) {
		if(i<n) {
			upd1(T[i].nd, 1);
			upd2(T[i].nd, T[i].st);
		}
		if(mid==i && ma==0) {
			ma=0;
			gdzie=i;
		}
		if(0<mid-i && mid-i<=i+1) {
			ll p=cnt(0, znajdz(mid-i));
			if(p>ma) {
				ma=p;
				gdzie=i;
			}
		}
	}
	for(int i=r; i>=gdzie; --i) {
		if(i<n) {
			upd1(T[i].nd, -1);
			upd2(T[i].nd, -T[i].st);
		}
	}
	dc(gdzie, r, mid+1, b, n);
	for(int i=gdzie-1; i>=l; --i) {
		if(i<n) {
			upd1(T[i].nd, -1);
			upd2(T[i].nd, -T[i].st);
		}
	}
	dc(l, gdzie, a, mid-1, n);
	ans[mid]=ma;
}
vector<ll>licz(vector<ll>V) {
	int n=V.size();
	N=1;
	while(N<2*n) N*=2;
	rep(i, 2*N) ile[i]=ans[i]=sum[i]=0;
	rep(i, n) P[i]={V[i], i};
	sort(P, P+n);
	reverse(P, P+n);
	rep(i, n) T[P[i].nd]={P[i].st, i};
	dc(0, n-1, 0, 2*n-1, n);
	vector<ll>W;
	rep(i, 2*n) W.pb(ans[i]);
	return W;
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	vector<ll>V, A1, A2, B1, B2;
	for(int i=start; i<n; ++i) V.pb(attraction[i]);
	A1=licz(V);
	V.clear();
	for(int i=start; i<n; ++i) {
		V.pb(attraction[i]);
		V.pb(0);
	}
	A2=licz(V);
	V.clear();
	V.pb(0);
	for(int i=start-1; i>=0; --i) V.pb(attraction[i]);
	B1=licz(V);
	V.clear();
	V.pb(0);
	for(int i=start-1; i>=0; --i) {
		V.pb(0);
		V.pb(attraction[i]);
	}
	B2=licz(V);
	ll ma=0;
	rep(i, min(int(A1.size()), d+1)) {
		ma=max(ma, A1[i]+B2[min(d-i, int(B2.size()-1))]);
	}
	rep(i, min(int(A2.size()), d+1)) {
		ma=max(ma, A2[i]+B1[min(d-i, int(B1.size()-1))]);
	}
	return ma;
}

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