| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1066398 | Nika533 | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
const int NN=1e5+5;
int n,d,st;
long long arr[NN],f[NN*3],ind[NN];
struct segmentTree {
struct node {
long long val=0,cnt=0;
};
vector<node> t;
void build(int v, int tl, int tr) {
t.push_back({0,0});
if (tl==tr) return;
int mid=(tl+tr)/2;
build(v*2,tl,mid); build(v*2+1,mid+1,tr);
}
void update(int v, int tl, int tr, int ind, long long a, long long b) {
if (tl==tr) {
t[v].val+=a; t[v].cnt+=b; return;
}
int mid=(tl+tr)/2;
if (ind<=mid) update(v*2,tl,mid,ind,a,b);
else update(v*2+1,mid+1,tr,ind,a,b);
t[v].val=t[v*2].val+t[v*2+1].val; t[v].cnt=t[v*2].cnt+t[v*2+1].cnt;
}
long long query(int v, int tl, int tr, int k) {
if (k<=0) return 0;
if (v>=t.size()) return 0;
if (t[v].cnt<=k) return t[v].val;
int mid=(tl+tr)/2;
long long res=query(v*2,tl,mid,k);
if (t[v*2].cnt<k) res+=query(v*2+1,mid+1,tr,k-t[v*2].cnt);
return res;
}
} segtree;
void solve(int tl, int tr, int l, int r, int x) {
if (tl>tr) return;
int mid=(tl+tr)/2;
long long mx_num=0; int mx_ind=0;
for (int i=l; i<=r; i++) {
segtree.update(1,st,n-1,ind[i],arr[i],1);
long long num=segtree.query(1,st,n-1,mid-(i-st)*x);
if (num>mx_num) {
mx_num=num; mx_ind=i;
}
}
f[mid]=mx_num;
for (int i=l; i<=r; i++) segtree.update(1,st,n-1,ind[i],-arr[i],-1);
for (int i=l; i<mx_ind; i++) segtree.update(1,st,n-1,ind[i],arr[i],1);
solve(mid+1,tr,mx_ind,r,x);
for (int i=l; i<mx_ind; i++) segtree.update(1,st,n-1,ind[i],-arr[i],-1);
solve(tl,mid-1,l,mx_ind,x);
}
long long cal() {
if (st==0) return 0;
pair<int,int> arr2[n];
for (int i=0; i<n; i++) arr2[i]={arr[i],i};
sort(arr2+st,arr2+n); reverse(arr2+st,arr2+n);
for (int i=0; i<n; i++) ind[arr2[i].second]=i;
segtree.t.clear(); segtree.build(1,st,n-1);
solve(0,d,st,n-1,2);
long long f1[d+1];
for (int i=0; i<=d; i++) f1[i]=f[i];
reverse(arr,arr+n); int in_st=st;
st=n-1-st; st++;
for (int i=0; i<n; i++) arr2[i]={arr[i],i};
sort(arr2+st,arr2+n); reverse(arr2+st,arr2+n);
for (int i=0; i<n; i++) ind[arr2[i].second]=i;
segtree.t.clear(); segtree.build(1,st,n-1);
solve(0,d,st,n-1,1);
st=in_st; reverse(arr,arr+n);
long long f2[d+1];
for (int i=0; i<=d; i++) f2[i]=f[i];
long long ans=0;
for (int i=0; i<=d-1; i++) {
int j=d-i-1;
ans=max(ans,f1[i]+f2[j]);
}
return ans;
}
long long findMaxAttraction(int N, int START, int D, const int attraction[]) {
n=N; st=START; d=D;
for (int i=0; i<n; i++) arr[i]=attraction[i];
long long ans1=cal(); reverse(arr,arr+n); st=n-1-st; long long ans2=cal();
return max(ans1,ans2);
}