제출 #1267397

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1267397		elotelo966	휴가 (IOI14_holiday)	C++20	23 / 100	118 ms	6984 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define OYY LLONG_MAX
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fi first
#define se second
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define pb push_back
#define lim 100005

typedef long long lo;

int st,dist,n;

int dizi[lim];

lo cev;

int a[lim],val[lim];

lo tree[4*lim][2];// val_top - kac_tane

int cur_l=1,cur_r=1;

inline int cal(int x,int y){
	int sol=abs(x-st);
	int sag=abs(y-st);
	return sol+sag+min(sol,sag);
}

inline void update(int node,int start,int end,int l,int r,lo val,lo ekle){
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		tree[node][0]+=ekle*val;
		tree[node][1]+=ekle;
		return ;
	}
	update(node*2,start,mid,l,r,val,ekle),update(node*2+1,mid+1,end,l,r,val,ekle);
	tree[node][0]=tree[node*2][0]+tree[node*2+1][0];
	tree[node][1]=tree[node*2][1]+tree[node*2+1][1];
}

inline void upd(int l,int r){
	while(l<cur_l){
		cur_l--;
		update(1,1,n,a[cur_l],a[cur_l],val[a[cur_l]],1);
	}
	while(r>cur_r){
		cur_r++;
		update(1,1,n,a[cur_r],a[cur_r],val[a[cur_r]],1);
	}
	while(l>cur_l){
		update(1,1,n,a[cur_l],a[cur_l],val[a[cur_l]],-1);
		cur_l++;
	}
	while(r<cur_r){
		update(1,1,n,a[cur_r],a[cur_r],val[a[cur_r]],-1);
		cur_r--;
	}
}

inline lo query(int node,int start,int end,int kalan){
	if(start==end || kalan==0){
		return tree[node][0];
	}
	lo sag=tree[node*2+1][1];
	if(sag>=kalan){// saga dallan
		return query(node*2+1,mid+1,end,kalan);
	}
	else{
		return tree[node*2+1][0]+query(node*2,start,mid,kalan-sag);
	}
}

inline void dnq(int l,int r,int optl,int optr){
	if(l>r)return ;
	int mi=(l+r)/2;
	int opt=optl;
	lo best=-1;
	for(int i=optl;i<=min(optr,mi);i++){
		int git=cal(i,mi);
		if(git>dist)continue;
		int kalan=dist-git;
		upd(i,mi);
		lo cur_cev=0;
		if(tree[1][1]<=kalan){
			cur_cev=tree[1][0];
		}
		else{
			cur_cev=query(1,1,n,kalan);
		}
		if(cur_cev>best){
			best=cur_cev;
			opt=i;
		}
		cev=max(cev,cur_cev);
	}
	dnq(l,mi-1,optl,opt),dnq(mi+1,r,opt,optr);
}

long long int findMaxAttraction(int nm, int start, int d, int attraction[]) {
	st=start+1;
	dist=d;
	n=nm;
	
	cev=0;
	
	vector<pair<int,int>> v;
	
	FOR{
		dizi[i]=attraction[i-1];
		v.pb({dizi[i],i});
	}
	
	sort(v.begin(),v.end());
	
	for(int i=0;i<n;i++){
		a[v[i].se]=i+1;
		val[i+1]=v[i].fi;
	}
	
	update(1,1,n,a[1],a[1],val[a[1]],1);
		
	dnq(st,n,1,st);
	
	return cev;
}

//~ int main(){
	//~ faster
	//~ int n,start,d;
	//~ cin>>n>>start>>d;
	//~ int arr[n];
	//~ FOR{
		//~ cin>>arr[i-1];
	//~ }
	//~ lo cev=findMaxAttraction(n,start,d,arr);
	//~ cout<<cev<<'\n';
	//~ return 0;
//~ }

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