제출 #254821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254821		b00n0rp	휴가 (IOI14_holiday)	C++17	23 / 100	578 ms	11112 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pb push_back

#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const int MX = 100005;

int ans = 0,N,D,S;

pii a[MX];

struct node{
	int cnt,sum;
	node(){
		cnt = 0;
		sum = 0;
	}
} seg[4*MX];

void upd(int ind,int l,int r,int pos,int val,int type){
	if(pos < l or pos > r) return;
	if(l == r){
		seg[ind].cnt = type;
		seg[ind].sum = val*type;
		// trace(ind,l,r,pos,val,type,seg[ind].cnt,seg[ind].sum);
		return;
	}
	int m = (l+r)/2;
	upd(2*ind,l,m,pos,val,type);
	upd(2*ind+1,m+1,r,pos,val,type);
	seg[ind].cnt = seg[2*ind].cnt+seg[2*ind+1].cnt;
	seg[ind].sum = seg[2*ind].sum+seg[2*ind+1].sum;
	// trace(ind,l,r,pos,val,type,seg[ind].cnt,seg[ind].sum);
}

int quer(int ind,int l,int r,int rem){
	// trace(ind,l,r,rem);
	if(l == r){
		if(rem) return seg[ind].sum;
		else return 0;
	}
	int m = (l+r)/2;
	if(seg[2*ind+1].cnt >= rem) return quer(2*ind+1,m+1,r,rem);
	else return seg[2*ind+1].sum+quer(2*ind,l,m,rem-seg[2*ind+1].cnt);
}

void solve(int l,int r,int optl,int optr){
	// assumes r+1...optl-1 are already activated in segtree
	// trace(l,r,optl,optr);
	int mid = (l+r)/2;
	if(S-mid >= D){
		if(mid != r) solve(mid+1,r,optl,optr);
		return;
	}
	int cur = -1,opt = optl;
	FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
	// trace(l,r,optl,optr);
	FOR(i,optl,optr+1){
		upd(1,0,N-1,a[i].S,a[i].F,1);
		int rem = D-2*min(S-mid,i-S)-max(S-mid,i-S);
		if(rem <= 0) break;
		int gg = quer(1,0,N-1,rem);
		// trace(mid,i,rem,gg);
		if(gg > cur){
			cur = gg;
			opt = i;
		}
	}
	if(cur > ans) ans = cur;
	FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
	FOR(i,optl,optr+1) upd(1,0,N-1,a[i].S,a[i].F,0);

	if(l != mid){
		FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,1);
		solve(l,mid-1,optl,opt);
		FOR(i,mid,r+1) upd(1,0,N-1,a[i].S,a[i].F,0);
	}
	if(r != mid){
		FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,1);
		solve(mid+1,r,opt,optr);
		FOR(i,optl,opt) upd(1,0,N-1,a[i].S,a[i].F,0);
	}
}

int findMaxAttraction(signed n, signed start, signed d, signed attraction[]) {
	vector<pii> v;
	D = d;
	N = d;
	S = start;
	REP(i,n) v.pb({attraction[i],i});
	sort(v.begin(),v.end());
	REP(i,n) a[v[i].S] = {v[i].F,i};
	// REP(i,n){
	// 	trace(i,a[i].F,a[i].S);
	// }
	solve(0,start,start,n-1);
	return ans;
}

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