Submission #93820

#	Time	Username	Problem	Language	Result	Execution time	Memory
93820		Bodo171	Holiday (IOI14_holiday)	C++14	100 / 100	380 ms	5972 KiB

holiday

#include"holiday.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int nmax=100005;
pair<long long,long long> aib[nmax];
long long ans;
pair<int,int> norm[nmax];
int wh[nmax],v[nmax],opt[nmax];
long long mx[nmax];
int n,D;
inline int lbit(int x)
{
    return ((x^(x-1))&x);
}
void update(int poz,long long v1,long long v2)
{
    for(int idx=poz;idx<=n;idx+=lbit(idx))
            aib[idx].first+=v1,aib[idx].second+=v2;
}
long long find_kth(int k)
{
    int cat=0,poz=0;
    long long ret=0;
    for(int p=17;p>=0;p--)
    {
        if(poz+(1<<p)<=n&&cat+aib[poz+(1<<p)].first<=k)
        {
            poz+=(1<<p);
            cat+=aib[poz].first;
            ret+=aib[poz].second;
        }
    }
    return ret;
}
void add(int poz)
{
    update(wh[poz],1,v[poz]);
}
void rem(int poz)
{
    update(wh[poz],-1,-v[poz]);
}
long long qr(int st,int dr,int mm)
{
    long long rr=find_kth(D-2*(dr-mm)-(mm-st));
    ans=max(ans,rr);
    if(rr>mx[dr])
        mx[dr]=rr,opt[dr]=st;
    return rr;
}
void solve(int s,int st,int dr,int optst,int optdr)
{
    if(st>dr) return;
    int m=(st+dr)/2;
    for(int i=st;i<=m;i++)
    {
        add(i);
    }
    qr(optdr,m,s);
    for(int i=optdr-1;i>=optst;i--)
    {
        add(i);
        qr(i,m,s);
    }
    if(!opt[m]) opt[m]=optdr;
    for(int i=optst;i<optdr;i++)
        rem(i);
    solve(s,m+1,dr,opt[m],optdr);
    for(int i=opt[m];i<optdr;i++)
        add(i);
    for(int i=st;i<=m;i++)
        rem(i);
    solve(s,st,m-1,optst,opt[m]);
    for(int i=opt[m];i<optdr;i++)
        rem(i);

}
void solvebrut(int s)
{
    for(int i=s;i<=n;i++)
    {
        add(i);
        qr(s,i,s);
        for(int j=s-1;j>=1;j--)
        {
            add(j);
            qr(j,i,s);
        }
        for(int j=s-1;j>=1;j--)
            rem(j);
    }
    for(int i=s;i<=n;i++)
        rem(i);
}
long long int findMaxAttraction(int N, int start, int d, int attraction[]) {
    n=N;
    for(int i=1;i<=n;i++)
        v[i]=attraction[i-1];
    for(int i=1;i<=n;i++)
        norm[i].first=v[i],norm[i].second=i;
    sort(norm+1,norm+n+1);
    for(int i=1;i<=n;i++)
        wh[norm[i].second]=n-i+1;
    D=d;
    start++;
    solve(start,start,n,1,start);
    //if(n<=3000||start<=100||start>=n-100) solvebrut(start);
    for(int i=1;i<=n;i++)
        mx[i]=0,opt[i]=0;
    for(int i=1;i<=n/2;i++)
        swap(v[i],v[n-i+1]),swap(wh[i],wh[n-i+1]);
    solve(n-start+1,n-start+1,n,1,n-start+1);
   // if(n<=3000||start<=100||start>=n-100) solvebrut(n-start+1);
    return ans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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