| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 93705 | jangwonyoung | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
ll m,boss;
vector<pair<ll,pair<ll,ll> > >hbit[100001];
pair<ll,ll>bit[100001];
ll a[100001];
pair<ll,ll>b[100001];
ll p[100001];
ll st;
ll ans1[300001],ans2[300001],ans3[300001],ans4[300001];
vector<pair<ll,ll> >good;
ll sch(ll v){
ll res=0LL;
ll fnd=0LL;
for(ll i=16; i>=0LL ;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;
}
ll getc(ll x,ll y,ll d,ll dx){
ll cur=0LL;
ll res=d*abs(x-st);
ll val=0LL;
for(ll i=16; i>=0LL ;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,0LL)));
ll 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(ll id,ll pos,ll v,ll dx){
for(ll 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(ll id,ll d,ll dx){
upd(id,p[id],a[id],dx);
if(good.empty()){
good.push_back({id,0LL});
return;
}
ll 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});
}
void init(){
for(ll i=1; i<=m ;i++){
hbit[i].clear();
hbit[i].push_back({0LL,{0LL,0LL}});
}
}
bool debug=false;
void cal(ll* ans,ll d,ll en,ll s,ll e,ll dx){
for(ll i=1; i<=m ;i++){
hbit[i].clear();
hbit[i].push_back({0LL,{0LL,0LL}});
bit[i]={0LL,0LL};
}
for(ll i=s; i!=e+dx ;i+=dx) add(i,d,dx);
for(ll i=1; i<=m ;i++){
hbit[i].clear();
hbit[i].push_back({0LL,{0LL,0LL}});
bit[i]={0LL,0LL};
}
if(good.empty()) return;
ll ptr=-1;
ll cur=s-dx;
for(ll i=0LL; i<=en ;i++){
if(ptr<(ll)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);
}
good.clear();
}
ll findMaxAttraction(ll n, ll start, ll d, ll attraction[]) {
m=n;boss=d;
st=start+1;
for(ll i=1; i<=n ;i++){
a[i]=attraction[i-1];
b[i]={a[i],i};
}
sort(b+1,b+n+1);
for(ll 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=0LL;
for(ll i=0LL; i<=d ;i++){
fans=max(fans,ans1[i]+ans2[d-i]);
fans=max(fans,ans3[i]+ans4[d-i]);
}
return fans;
}