oj.uz

답안 #93709

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
93709 2019-01-10T21:11:06 Z jangwonyoung 휴가 (IOI14_holiday) C++14
100 / 100
 1494 ms 50092 KB 
#include<cstdio>
#include"holiday.h"
#include"holiday.h"
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
int m,boss;
vector<pair<int,pair<ll,int> > >hbit[100001];
pair<ll,int>bit[100001];
ll a[100001];
pair<ll,int>b[100001];
int p[100001];
int st;
ll ans1[300001],ans2[300001],ans3[300001],ans4[300001];
vector<pair<int,int> >good;
ll sch(int v){
	ll res=0;
	int fnd=0;
	for(int i=16; i>=0 ;i--){
		if((fnd|(1<<i))<=m && bit[fnd|(1<<i)].se<=v){
			fnd|=(1<<i);
			v-=bit[fnd].se;
			res+=bit[fnd].fi;
		}
	}
	return res;
}
int getc(int x,int y,int d,int dx){
	int cur=0;
	int res=d*abs(x-st);
	ll val=0;
	for(int i=16; i>=0 ;i--){
		if((cur|(1<<i))>m) continue;
		auto tmp=*--lower_bound(hbit[cur|(1<<i)].begin(),hbit[cur|(1<<i)].end(),make_pair(x*dx+1,make_pair(0LL,0)));
		int newi=res+tmp.se.se;
		ll newv=val+tmp.se.fi;
		if(newi<d*abs(y-st)){cur|=(1<<i);res=newi;val=newv;continue;}
		ll myv=sch(newi-d*abs(y-st));
		if(myv<newv){cur|=(1<<i);res=newi;val=newv;}
	}
	return res+1;
}
void upd(int id,int pos,ll v,int dx){
	for(int i=pos; i<=m ;i+=i&-i){
		bit[i]={bit[i].fi+v,bit[i].se+1};
		hbit[i].push_back({id*dx,bit[i]});
	}
}
void add(int id,int d,int dx){
	upd(id,p[id],a[id],dx);
	if(good.empty()){
		good.push_back({id,0});
		return;
	}
	int last=getc(good.back().fi,id,d,dx);
	while(good.size()>1 && good.back().se>=last){
		good.pop_back();
		last=getc(good.back().fi,id,d,dx);
	}
	good.push_back({id,last}); 
}
bool debug=false;
void cal(ll* ans,int d,int en,int s,int e,int dx){
	en=min(en,boss);
	for(int i=1; i<=m ;i++){
		hbit[i].clear();
		hbit[i].push_back({st*dx,{0LL,0}});
		bit[i]={0LL,0};
	}
	for(int i=s; i!=e+dx ;i+=dx) add(i,d,dx);
	for(int i=1; i<=m ;i++){
		hbit[i].clear();
		hbit[i].push_back({st*dx,{0LL,0}});
		bit[i]={0LL,0};
	}
	if(good.empty()) return;
	int ptr=-1;
	int cur=s-dx;
	for(int i=0; i<=en ;i++){
		if(ptr<(int)good.size()-1 && good[ptr+1].se==i){
			ptr++;
			while(cur!=good[ptr].fi){
				cur+=dx;
				upd(cur,p[cur],a[cur],dx);
			}
		}
		ans[i]=sch(i-abs(cur-st)*d);
		if(i!=0) ans[i]=max(ans[i],ans[i-1]);
	}
	for(int i=en+1; i<=boss ;i++) ans[i]=ans[i-1];
	good.clear();
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	m=n;boss=d;
    st=start+1;
    for(int i=1; i<=n ;i++){
    	a[i]=attraction[i-1];
    	b[i]={a[i],i};
	}
    sort(b+1,b+n+1);
    for(int i=1; i<=n ;i++) p[b[i].se]=n+1-i;
    cal(ans1,2,(n-st)*3+1,st,n,1);
    cal(ans2,1,(st-1)*2,st-1,1,-1);
    cal(ans3,2,(st-1)*3,st-1,1,-1);
    cal(ans4,1,(n-st)*2+1,st,n,1);
    ll fans=0;
    for(int i=0; i<=d ;i++){
    	fans=max(fans,ans1[i]+ans2[d-i]);
    	fans=max(fans,ans3[i]+ans4[d-i]);
	}
    return fans;
}

Compilation message

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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 3 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 3 ms 2680 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 46948 KB Output is correct
2 Correct 394 ms 46888 KB Output is correct
3 Correct 325 ms 46880 KB Output is correct
4 Correct 425 ms 47784 KB Output is correct
5 Correct 1196 ms 43356 KB Output is correct
6 Correct 282 ms 16500 KB Output is correct
7 Correct 590 ms 24816 KB Output is correct
8 Correct 746 ms 29288 KB Output is correct
9 Correct 192 ms 14256 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 3960 KB Output is correct
2 Correct 9 ms 3960 KB Output is correct
3 Correct 9 ms 3960 KB Output is correct
4 Correct 16 ms 3448 KB Output is correct
5 Correct 15 ms 3448 KB Output is correct
6 Correct 7 ms 3064 KB Output is correct
7 Correct 6 ms 2936 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 6 ms 2936 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 292 ms 50092 KB Output is correct
2 Correct 468 ms 47776 KB Output is correct
3 Correct 505 ms 15084 KB Output is correct
4 Correct 16 ms 3452 KB Output is correct
5 Correct 7 ms 2936 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 7 ms 2936 KB Output is correct
8 Correct 1494 ms 30696 KB Output is correct
9 Correct 1417 ms 30560 KB Output is correct