oj.uz

Submission #638953

# Submission time Handle Problem Language Result Execution time Memory
638953 2022-09-08T04:30:25 Z ggoh Holiday (IOI14_holiday) C++14
100 / 100
 3491 ms 49868 KB 
#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;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 692 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49172 KB Output is correct
2 Correct 50 ms 49092 KB Output is correct
3 Correct 50 ms 49128 KB Output is correct
4 Correct 49 ms 49204 KB Output is correct
5 Correct 64 ms 45016 KB Output is correct
6 Correct 16 ms 13264 KB Output is correct
7 Correct 35 ms 24364 KB Output is correct
8 Correct 40 ms 29584 KB Output is correct
9 Correct 11 ms 9416 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 2 ms 1856 KB Output is correct
3 Correct 2 ms 1748 KB Output is correct
4 Correct 40 ms 1748 KB Output is correct
5 Correct 28 ms 1616 KB Output is correct
6 Correct 2 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 5 ms 980 KB Output is correct
9 Correct 5 ms 980 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 49800 KB Output is correct
2 Correct 50 ms 49868 KB Output is correct
3 Correct 349 ms 21592 KB Output is correct
4 Correct 18 ms 1748 KB Output is correct
5 Correct 5 ms 980 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 5 ms 980 KB Output is correct
8 Correct 3491 ms 49728 KB Output is correct
9 Correct 3403 ms 49732 KB Output is correct