제출 #638953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638953		ggoh	휴가 (IOI14_holiday)	C++14	100 / 100	3491 ms	49868 KiB

holiday

#include<bits/stdc++.h>
#include "holiday.h"
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
int n,m,D,st,sz,root[100005],a[100005],go[100005];
lint ans;
 
struct PST{
    int cnt;
    lint sum;
    int l,r;
} T[3500000];
void init(int num,int s,int e)
{
    if(s==e)return ;
    T[num].l=sz++;
    T[num].r=sz++;
    init(T[num].l,s,(s+e)/2);
    init(T[num].r,(s+e)/2+1,e);
}
void update(int par, int num, int s, int e, int i)
{
    T[num].cnt=T[par].cnt + 1;
    T[num].sum=T[par].sum + a[i];
    if(s==e)return ;
    int m=(s+e)/2;
    if(m>=go[i])
    {
        T[num].r=T[par].r;
        T[num].l=sz++;
        update(T[par].l,T[num].l,s,m,i);
    }
    else
    {
        T[num].l=T[par].l;
        T[num].r=sz++;
        update(T[par].r,T[num].r,m+1,e,i);
    }
}
lint getmaxk(int num, int k)
{
    if(k==0)return 0;
    if(k==T[num].cnt)return T[num].sum;
    if(T[T[num].r].cnt >= k)
    {
        return getmaxk(T[num].r,k);
    }
    else 
    {
        return T[T[num].r].sum + getmaxk(T[num].l,k - T[T[num].r].cnt);
    }
}
 
lint g(int l,int r,int k)
{
    if(k>r-l+1)k=r-l+1;
    lint ret1,ret2,ret=0;
    int p=max(0,k-(st-l));
    int q=min(k,r-st+1);
    while(q-p>2)
    {
        int h=(p+q)/2;
        ret1=getmaxk(root[r],h)+(l==st?0:getmaxk(root[l],k-h));
        ret2=getmaxk(root[r],h+1)+(l==st?0:getmaxk(root[l],k-h-1));
        if(ret1==ret2)p=q=h;
        else if(ret1<ret2)p=h;
        else q=h+1;
    }
    for(int i=p;i<=q;i++)
    {
        ret=max(ret,getmaxk(root[r],i)+(l==st?0:getmaxk(root[l],k-i)));
    }
 
    return ret;
}
void f(int p,int q,int optp,int optq,int dir)
{
    if(p>q)return ;
    int h=(p+q)/2;
    int opth;
    lint tmp,maxi=-1e9;
    for(int j=optp;j<=optq;j++)
    {
        if(dir)tmp=g(j,h,max(D-(st+h-2*j),0));
        else tmp=g(h,j,max(D+(st+h-2*j),0));
        if(tmp>maxi)
        {
            maxi=tmp;
            opth=j;
        }
    }
    if(maxi>ans)ans=maxi;
    f(p,h-1,optp,opth,dir);
    f(h+1,q,opth,optq,dir);
}
 
lint findMaxAttraction(int N, int start, int d, int attraction[])
{
  st=start;n=N;D=d;
  for(int i=0;i<n;i++)a[i]=attraction[i];
  vector<pii>V;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
        V.push_back({a[i],i});
    }
    sort(V.begin(),V.end());
    for(int i=0;i<n;i++)go[V[i].second]=i;
    sz=1;
    init(0,0,n-1);
    for(int i=0;i<n;i++)root[i]=sz++;
    for(int i=st;i<n;i++)update(i==st? 0 : root[i-1], root[i], 0, n-1, i);
    for(int i=st-1;i>=0;i--)update(i==st-1? 0 : root[i+1], root[i], 0, n-1, i);
    f(st,n-1,0,st,1);
    f(0,st,st,n-1,0);
  return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

holiday.cpp: In function 'lint findMaxAttraction(int, int, int, int*)':
holiday.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
holiday.cpp: In function 'void f(int, int, int, int, int)':
holiday.cpp:96:6: warning: 'opth' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |     f(p,h-1,optp,opth,dir);
      |     ~^~~~~~~~~~~~~~~~~~~~~

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