Submission #1064983

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064983		Edu175	Holiday (IOI14_holiday)	C++17	100 / 100	369 ms	19488 KiB

holiday

#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fdgkj:v)cout<<fdgkj<<" ";cout<<endl;}
#define impr(v) {cout<<"{ ";for(auto fdgkj:v)cout<<fdgkj<<" ";cout<<"}";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=1e5+5;

ii NEUT={0,0};
ii oper(ii a, ii b){
	return {a.fst+b.fst,a.snd+b.snd};
}
ll tec(ll n){
	ll res=0;
	while(n>1)res++,n=(n+1)/2;
	return 1ll<<res;
}
struct STree{
	ll n; vector<ii>t; vector<ll>a,idx;
	STree(){}
	STree(vector<ll>A):n(tec(SZ(A))),t(2*n+5,NEUT),a(A){
		a.resize(n);
		vector<ii>b;
		fore(i,0,n)b.pb({a[i],i});
		sort(ALL(b));
		idx=vector<ll>(n);
		fore(i,0,n){
			idx[b[i].snd]=i;
		}
	}
	void upd(ll p, ll fg){ // 1 add, 0 remove
		// cout<<"upd "<<p<<"("<<n<<") "<<SZ(a)<<" --> ";
		ll i=p;
		p=idx[p];
		// cout<<p<<endl;
		p+=n;
		t[p]={fg,fg*a[i]};
		for(;p>1;p>>=1)t[p>>1]=oper(t[p],t[p^1]);
	}
	ll p=0;
	void adjust(ll m){
		m++;
		while(p<m)upd(p++,1);
		while(p>m)upd(--p,0);
	}
	ll find(ll k, ll v){
		if(k>=n)return v>0?t[k].snd:0;
		if(t[2*k+1].fst<=v){
			return t[2*k+1].snd+find(2*k,v-t[2*k+1].fst);
		}
		return find(2*k+1,v);
	}
	ll query(ll v){
		return find(1,v);
	}
};
ll val[3*MAXN];
STree st;
ll fg;
void dnc(ll l, ll r, ll s, ll e){
	// cout<<"dnc "<<l<<","<<r<<" "<<s<<","<<e<<endl;
	ll m=(l+r)/2;
	ll opt=0, &res=val[m]; res=-1;
	fore(i,s,e){
		st.adjust(i);
		ll di=m-(1+fg)*i;
		ll resi=st.query(di);
		if(resi>res)opt=i,res=resi;
	}
	if(r-l>1){
		dnc(l,m,s,opt+1);
		dnc(m+1,r,opt,e);
	}
}
vector<ll> getds(vector<ll>a, ll d, ll _fg){
	// cout<<"getds: "<<fg<<", "; imp(a); 
	ll n=SZ(a);
	fg=_fg;
	st=STree(a);
	vector<ll>res(d);
	if(!SZ(a))return res;
	dnc(0,d,0,n);
	fore(i,0,d)res[i]=val[i];
	// cout<<" = "; imp(res); 
	return res;
}

long long findMaxAttraction(int N, int s, int d, int A[]) {
	ll n=N;
	vector<ll>a(n);
	fore(i,0,n)a[i]=A[i];
	vector<ll>l,r;
	fore(i,0,n){
		if(i<s)l.pb(a[i]);
		else r.pb(a[i]);
	}
	reverse(ALL(l));
	ll res=0;
	fore(fg,0,2){
		auto lhs=getds(l,d+2,fg);
		auto rhs=getds(r,d+2,fg^1);
		fore(i,0,fg+1)lhs.insert(lhs.begin(),0);
		fore(i,0,d+1)res=max(res,lhs[i]+rhs[d-i]);
	}
	return res;
}

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