제출 #49001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49001		Namnamseo	휴가 (IOI14_holiday)	C++17	100 / 100	2451 ms	7512 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

ll inf = (1LL << 60);

vector<int> xp;

struct KF {
	const static int M = 131072;
	int tree[M<<1];
	ll  tsum[M<<1];
	void init(){
		for(auto& x:tree) x=0;
		for(auto& x:tsum) x=0;
	}
	
	void app(int x, int d){
		int p=lower_bound(all(xp), x) - xp.begin();
		p += M;
		while(p){
			tree[p] += d;
			tsum[p] += d*x;
			p >>= 1;
		}
	}
	void add(int x){ app(x, 1); }
	void del(int x){ app(x, -1); }
	
	ll topk(int k){
		if(k > tree[1]) k=tree[1];
		if(k == 0) return 0ll;
		ll ret=0;
		int p=1;
		while(p < M){
			if(k > tree[p*2+1]){
				k -= tree[p*2+1];
				ret += tsum[p*2+1];
				p *= 2;
			} else p = p*2+1;
		}
		return ret + k*1LL*xp[p-M];
	}
} kfinder;

int cur_l, cur_r;

ll ask(vector<int>& data, int l, int r, int d){
	while(cur_r < r) kfinder.add(data[++cur_r]);
	while(l < cur_l) kfinder.add(data[--cur_l]);
	while(r < cur_r) kfinder.del(data[cur_r--]);
	while(cur_l < l) kfinder.del(data[cur_l++]);
	return kfinder.topk(d);
}

ll work(vector<int> data, int sp, int days){
	int n = data.size();
	kfinder.init(); cur_l = 1, cur_r = 0;
	typedef tuple<int,int,int,int> state;
	queue<state> q; q.push(state{0, sp, 0, n-1});
	ll ans = -inf;
	while(q.size()){
		int ml, mr, xl, xr;
		tie(ml, mr, xl, xr) = q.front(); q.pop();
		int p=(ml+mr)/2;
		pair<ll,int> tmp(-inf, -1);
		for(int i=xl; i<=xr; ++i){
			if(p <= i && (sp-p) + (i-p) <= days)
				tmp=max(tmp, make_pair(ask(data, p, i, days-(sp-p)-(i-p)), i));
		}
		ans = max(ans, tmp.first);
		int use=tmp.second;
		if(ml <= p-1)
			q.push(state{ml, p-1, xl, use});
		if(p+1 <= mr)
			q.push(state{p+1, mr, use, xr});
	}
	return ans;
}


ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	vector<int> p(attraction, attraction+n);
	xp = p;
	sort(all(xp)); xp.erase(unique(all(xp)), xp.end());
	// do left side
	ll ans=work(p, start, d);
	// flip
	reverse(all(p)); start=n-1-start;
	// do right side
	ans=max(ans, work(p, start, d));
	// print ans
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'void read(int&)':
holiday.cpp:6:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~
grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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