| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 362748 | Dymo | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =2e5+10;
const ll mod=1e9+7;
const ll base=1e15;
ll st[maxn];
ll st1[maxn];
ll val[maxn];
ll pos[maxn];
struct tk
{
ll n;
ll l=1;
ll r=0;
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left)
return ;
if (left==right)
{
st[id]+=diff;
st1[id]+=val[left]*diff;
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid, x, diff);
update(id*2+1,mid+1, right, x, diff);
st[id]=st[id*2]+st[id*2+1];
st1[id]=st1[id*2]+st1[id*2+1];
}
void finit(ll n1)
{
l=1;
r=0;
init(1,1,n1);
n=n1;
}
void init(ll id,ll left,ll right)
{
st[id]=0;
st1[id]=0;
if (left==right)
return ;
ll mid=(left+right)/2;
init(id*2,left,mid);
init(id*2+1,mid+1, right);
}
void ers(ll t)
{
update(1,1,n,t,-1);
}
void add(ll t)
{
update(1,1,n,t,1);
}
ll get1(ll lf,ll rt,ll x)
{
if (x<0) return -1e15;
while (l>lf)
{
l--;
add(pos[l]);
}
while (l<lf)
{
ers(pos[l]);
l++;
}
while (r<rt)
{
r++;
add(pos[r]);
}
while (r>rt)
{
ers(r);
r--;
}
if (x>st[1])
{
return st1[1];
}
return get(1,1,n,x);
}
ll get(ll id,ll left,ll right,ll x)
{
if (left==right)
{
return val[left]*x;
}
ll mid=(left+right)/2;
if (st[id*2+1]<x)
{
return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1];
}
else
{
return get(id*2+1,mid+1,right,x);
}
}
} man;
ll ans[maxn];
void dac(ll start,ll l,ll r,ll low,ll high,ll d)
{
if (l>r) return ;
ll mid=(l+r)/2;
ll pos_best=-1;
ans[mid]=-1e15;
for (int i=low;i<=high;i++)
{
ll kc=mid-start;
if (i!=start)
{
kc+=mid-i;
}
ll t=man.get1(i,mid,d-kc);
if (ans[mid]<t)
{
ans[mid]=t;
pos_best=i;
}
}
dac(start,l,mid-1,low,pos_best,d);
dac(start,mid+1,r,pos_best,high,d);
}
ll dosth(ll start,ll n,ll d)
{
dac(start,1,start,start,min(n,start+d),d);
ll res=0;
for (int i=1;i<=n;i++)
{
res=max(res,ans[i]);
}
return res;
}
ll findMaxAttraction(ll n,ll start,ll d,ll attraction[])
{
vector<ll> vt;
for (int i=0; i<n; i++)
{
pos[i+1]=attraction[i];
vt.pb(pos[i+1]);
}
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
ll siz=vt.size();
for (int i=1; i<=siz; i++)
{
val[i]=vt[i-1];
}
for (int i=1; i<=n; i++)
{
pos[i]=lower_bound(vt.begin(),vt.end(),pos[i])-vt.begin()+1;
}
man.finit(n);
start++;
ll ans=dosth(start, n,d);
reverse(pos+1,pos+n+1);
ans=max(ans,dosth(n-start+1,n,d));
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
}*/