제출 #551848

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
551848		CSQ31	휴가 (IOI14_holiday)	C++17	100 / 100	650 ms	17448 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
typedef long long int ll;
ll t[4*MAXN];
int cnt[4*MAXN],idx[MAXN],N;
void upd(int v,int pos,int l,int r,int val,int c){
	if(l==r){
		t[v] = val;
		cnt[v] = c;
		return;
	}
	int tm = (l+r)/2;
	if(pos<=tm)upd(2*v,pos,l,tm,val,c);
	else upd(2*v+1,pos,tm+1,r,val,c);
	t[v] = t[2*v] + t[2*v+1];
	cnt[v] = cnt[2*v] + cnt[2*v+1];
}
void clr(int v,int l,int r){
	t[v] = cnt[v] = 0;
	if(l==r)return;
	int tm = (l+r)/2;
	clr(2*v,l,tm);
	clr(2*v+1,tm+1,r);
}
ll query(int v,int l,int r,int k){
	if(cnt[v] == k || l==r)return t[v];
	int tm = (l+r)/2;
	if(cnt[2*v+1] >= k)return query(2*v+1,tm+1,r,k);
	else return t[2*v+1] + query(2*v,l,tm,k-cnt[2*v+1]);
}
void add(int i,int val,int c){upd(1,idx[i]+1,1,N,val,c);}
ll rwalk[2][3*MAXN]; //walk right turn back
ll lwalk[2][3*MAXN]; //walk left turn back
int f[MAXN]; //optimal endpoint

long long int findMaxAttraction(int n, int start, int d, int a[]) {
	N = n;
	ll ans = 0;
	vector<pair<int,int>>b;
	for(int i=0;i<n;i++)b.push_back({a[i],i});
	sort(b.begin(),b.end());
	for(int i=0;i<n;i++)idx[b[i].second] = i;
	vector<array<int,4>>v;
	//walk right turn back
	if(start != n-1){
		v.push_back({start+1,n-1,0,d});
		while(!v.empty()){
			vector<array<int,4>>u;
			int cur = start+1;
			for(auto x:v){
				int l = x[0],r = x[1],L=x[2],R=x[3];
				int k = (L+R)/2;
				ll best = 0;
				f[k] = l;
				for(int i=l;i<=r;i++){
					int co = k-2*(i-start) + 1;
					if(co <= 0)break;
					while(cur<=i){
						add(cur,a[cur],1);
						cur++;
					}
					ll res = query(1,1,n,co);
					if(res > best){
						best = res;
						f[k] = i;
					}
				}
				rwalk[1][k] = best;
				if(L!=R){
					int mid = (L+R)/2;
					if(mid-1 >= L)u.push_back({l,f[k],L,mid-1});
					if(mid+1 <= R)u.push_back({f[k],r,mid+1,R});
				}
			}
			clr(1,1,n);
			v = u;
		}
	}
	//walk right dont turn back
	v.push_back({start,n-1,0,d+1});
	while(!v.empty()){
		vector<array<int,4>>u;
		int cur = start;
		for(auto x:v){
			int l = x[0],r = x[1],L=x[2],R=x[3];
			int k = (L+R)/2;
			ll best = 0;
			f[k] = l;
			for(int i=l;i<=r;i++){
				int co = k-(i-start+1);
				if(co <= 0)break;
				while(cur<=i){
					add(cur,a[cur],1);
					cur++;
				}
				ll res = query(1,1,n,co);
				if(res > best){
					best = res;
					f[k] = i;
				}
			}
			rwalk[0][k] = best;
			if(L!=R){
				int mid = (L+R)/2;
				if(mid-1 >= L)u.push_back({l,f[k],L,mid-1});
				if(mid+1 <= R)u.push_back({f[k],r,mid+1,R});
			}
		}
		clr(1,1,n);
		v = u;
	}

	//walk left turn back
	if(start){
		v.push_back({0,start-1,0,d});
		while(!v.empty()){
			vector<array<int,4>>u;
			int cur = start-1;
			for(auto x:v){
				int l = x[0],r = x[1],L=x[2],R=x[3];
				int k = (L+R)/2;
				ll best = 0;
				f[k] = r;
				for(int i=r;i>=l;i--){
					int co = k - 2*(start-i) + 1;
					if(co <= 0)break;
					while(cur>=i){
						add(cur,a[cur],1);
						cur--;
					}
					ll res = query(1,1,n,co);
					if(res > best){
						best = res;
						f[k] = i;
					}
				}
				//cout<<l<<" "<<r<<" "<<L<<" "<<R<<" "<<k<<" "<<best<<" "<<f[k]<<'\n';
				lwalk[1][k] = best;
				if(L!=R){
					int mid = (L+R)/2;
					if(mid-1 >= L)u.push_back({f[k],r,L,mid-1});
					if(mid+1 <= R)u.push_back({l,f[k],mid+1,R});
				}
			}
			clr(1,1,n);
			v = u;
		}
	}
	//walk left dont turn back
	v.push_back({0,start,0,d+1});
	while(!v.empty()){
		vector<array<int,4>>u;
		int cur = start;
		for(auto x:v){
			int l = x[0],r = x[1],L=x[2],R=x[3];
			int k = (L+R)/2;
			ll best = 0;
			f[k] = r;
			for(int i=r;i>=l;i--){
				int co = k - (start-i+1);
				if(co <= 0)break;
				while(cur>=i){
					add(cur,a[cur],1);
					cur--;
				}
				ll res = query(1,1,n,co);
				if(res > best){
					best = res;
					f[k] = i;
				}
			}
			lwalk[0][k] = best;
			if(L!=R){
				int mid = (L+R)/2;
				if(mid-1 >= L)u.push_back({f[k],r,L,mid-1});
				if(mid+1 <= R)u.push_back({l,f[k],mid+1,R});
			}
		}
		clr(1,1,n);
		v = u;
	}
	ans = max(lwalk[0][d+1],rwalk[0][d+1]);
	/*
	for(int i=0;i<=d;i++)cout<<rwalk[1][i]<<" ";
	cout<<'\n';
	for(int i=0;i<=d;i++)cout<<lwalk[1][i]<<" ";
	cout<<'\n';
    for(int i=0;i<=d;i++)cout<<rwalk[0][i]<<" ";
	cout<<'\n';
	for(int i=0;i<=d;i++)cout<<lwalk[0][i]<<" ";
	cout<<'\n';
	* */
	for(int i=0;i<=d;i++){
		ans = max(ans,lwalk[0][i]+rwalk[1][d-i]);
		ans = max(ans,rwalk[0][i]+lwalk[1][d-i]);
	}
	return ans;
}

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