제출 #519813

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
519813		AdamGS	휴가 (IOI14_holiday)	C++17	23 / 100	349 ms	16184 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=2e5+7;
int ile[4*LIM], N;
pair<ll,ll>T[LIM], P[LIM];
ll sum[4*LIM], ans[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 ans=sum[l];
	if(l!=r) ans+=sum[r];
	while(l/2!=r/2) {
		if(l%2==0) ans+=sum[l+1];
		if(r%2==1) ans+=sum[r-1];
		l/=2; r/=2;
	}
	return ans;
}
void dc(int l, int r, int a, int b) {
	if(b<a) return;
	int mid=(a+b)/2;
	ll ma=0, gdzie=l;
	for(int i=l; i<=r; ++i) {
		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) {
		upd1(T[i].nd, -1);
		upd2(T[i].nd, -T[i].st);
	}
	dc(gdzie, r, mid+1, b);
	for(int i=gdzie-1; i>=l; --i) {
		upd1(T[i].nd, -1);
		upd2(T[i].nd, -T[i].st);
	}
	dc(l, gdzie, a, mid-1);
	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);
	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;
	rep(i, n) V.pb(attraction[i]);
	vector<ll>A1=licz(V);
	return A1[min(int(A1.size()-1), d)];
}

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