제출 #1303785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303785		StefanSebez	휴가 (IOI14_holiday)	C++20	100 / 100	575 ms	36996 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,lg=18;
const ll INF=1e18;
void chmx(ll &x,ll y){x=max(x,y);}
int n,S,D,a[N];
int root[N],nc,lc[N*lg],rc[N*lg],num[N*lg];ll sum[N*lg];
void Update(int &c,int c1,int ss,int se,int qind,int x){
    c=++nc;lc[c]=lc[c1],rc[c]=rc[c1],num[c]=num[c1],sum[c]=sum[c1];
    if(ss==se){num[c]=1,sum[c]=x;return;}
    int mid=ss+se>>1;
    if(qind<=mid) Update(lc[c],lc[c1],ss,mid,qind,x);
    else Update(rc[c],rc[c1],mid+1,se,qind,x);
    num[c]=num[lc[c]]+num[rc[c]];
    sum[c]=sum[lc[c]]+sum[rc[c]];
}
ll Get(int c,int ss,int se,int qs,int qe){
    if(qs>qe||qe<ss||se<qs)return 0;
    if(qs<=ss&&se<=qe)return sum[c];
    int mid=ss+se>>1;return Get(lc[c],ss,mid,qs,qe)+Get(rc[c],mid+1,se,qs,qe);
}
int Walk(int cL,int cR,int ss,int se,int k){
    if(ss==se)return ss;
    int mid=ss+se>>1;
    if(num[lc[cR]]-num[lc[cL]]>=k)return Walk(lc[cL],lc[cR],ss,mid,k);
    return Walk(rc[cL],rc[cR],mid+1,se,k-(num[lc[cR]]-num[lc[cL]]));
}
void Clear(){
    for(int i=0;i<=n;i++)root[i]=0;
    for(int i=0;i<=nc;i++)lc[i]=rc[i]=num[i]=sum[i]=0;
    nc=0;
}
ll Cost(int l,int r,int k){
    k=min(k,r-l+1);
    int ind=Walk(root[l-1],root[r],0,n,k);
    return Get(root[r],0,n,0,ind)-Get(root[l-1],0,n,0,ind);
}
ll Solve(int ss,int se,int lo,int up){
    if(ss>se)return -INF;
    int mid=ss+se>>1,opt=0;
    ll res=-INF;
    for(int i=lo;i<=min(up,mid);i++){
        ll x=Cost(i,mid,D-(mid-S+mid-i));
        if(x>=res){res=x;opt=i;}
    }
    chmx(res,Solve(ss,mid-1,lo,opt));
    chmx(res,Solve(mid+1,se,opt,up));
    return res;
}
ll Calc(){
    ll res=-INF;
    int ind1[n+10]={0};iota(ind1+1,ind1+n+1,1);
    sort(ind1+1,ind1+n+1,[&](int i,int j){return a[i]>a[j];});
    int ind[n+10];for(int i=1;i<=n;i++)ind[ind1[i]]=i;
    for(int i=1;i<=n;i++) Update(root[i],root[i-1],0,n,ind[i],a[i]);
    chmx(res,Solve(S,n,1,S));
    for(int i=S;i<=n;i++)chmx(res,Cost(S,i,D-(i-S)));
    return res;
}
long long int findMaxAttraction(int n1, int start, int D1, int attraction[]){
    n=n1,D=D1;
    for(int i=1;i<=n;i++) a[i]=attraction[i-1];
    S=start+1;
    ll res=Calc();
    reverse(a+1,a+n+1);
    Clear();
    S=n+1-S;
    chmx(res,Calc());
    return res;
}

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