Submission #1318608

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318608		kerem	Holiday (IOI14_holiday)	C++20	100 / 100	317 ms	50888 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define emb emplace_back
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e9
typedef tuple<int,int,int,int> iiii;

struct Node{
	int64_t sum;
	int sz,l,r;
	Node(){sz=sum=l=r=0;}
	Node(int ll,int rr){sz=sum=0;l=ll;r=rr;}
};
vector<Node> st;
vector<int> root;
vector<int> zort;
int addNode(int l,int r){
	st.emplace_back(l,r);
	st.back().sz=st[l].sz+st[r].sz;
	st.back().sum=st[l].sum+st[r].sum;
	return st.size()-1;
}
int update(int node,int l,int r,int qx){
	if(l==r){
		int tmp=node;
		node=addNode(0,0);
		st[node].sz=st[tmp].sz+1;
		st[node].sum=st[tmp].sum+zort[qx];
		return node;
	}
	int mid=(l+r)/2;
	if(qx<=mid)
		return addNode(update(st[node].l,l,mid,qx),st[node].r);
	else
		return addNode(st[node].l,update(st[node].r,mid+1,r,qx));
}
int64_t query(int nodeL,int nodeR,int l,int r,int qk){
	if(qk==0) return 0;
	if(l==r) return 1LL*qk*zort[l];
	int t=st[st[nodeR].r].sz-st[st[nodeL].r].sz;
	int mid=(l+r)/2;
	if(qk>=t)
		return query(st[nodeL].l,st[nodeR].l,l,mid,qk-t)+(st[st[nodeR].r].sum-st[st[nodeL].r].sum);
	else
		return query(st[nodeL].r,st[nodeR].r,mid+1,r,qk);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	for(int i=0;i<n;i++)
		zort.pb(attraction[i]);
	sort(all(zort));
	zort.resize(unique(all(zort))-zort.begin());
	
    root.pb(addNode(0,0));
    for(int i=0;i<n;i++){
		int j=lower_bound(all(zort),attraction[i])-zort.begin();
		root.pb(update(root[i],0,zort.size()-1,j));
	}
	//~ cout << "yuppi" << endl;
	int64_t ans=0;
	queue<iiii> q;
	q.emplace(0,start,start,n-1);
	while(!q.empty()){
		int optl,optr,l,r;
		tie(optl,optr,l,r)=q.front();
		q.pop();
		if(l>r) continue;
		//~ cout << optl sp optr sp l sp r << endl;
		int mid=(l+r)/2;
		pair<int64_t,int> opt={0,start};
		for(int i=optl;i<=optr;i++){
			int t=(mid-i)+min(start-i,mid-start);
			if(t<d){
				int64_t val=query(root[i],root[mid+1],0,zort.size()-1,min(d-t,mid-i+1));
				opt=max(opt,make_pair(val,i));
			}
		}
		ans=max(ans,opt.first);
		if(l<r){
			q.emplace(optl,opt.second,l,mid-1);
			q.emplace(opt.second,optr,mid+1,r);
		}
	}
	return ans;
}

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