제출 #1180925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180925		AlgorithmWarrior	휴가 (IOI14_holiday)	C++20	24 / 100	60 ms	73948 KiB

holiday

#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;

void maxself(long long& x,long long val){
    if(x<val)
        x=val;
}

int const INF=1000000000;
int const MAX=6000100;
int const NMAX=200100;
int root[NMAX];
long long ans;

struct node{
    int cnt;
    long long sum;
    int lson,rson;
};

struct PST{
    node v[MAX];
    int total;
    void update(int nod,int past,int st,int dr,int poz){
        if(st==dr){
            v[nod].cnt=v[past].cnt+1;
            v[nod].sum=v[past].sum+poz;
        }
        else{
            int mij=(st+dr)/2;
            if(poz<=mij){
                v[nod].lson=++total;
                v[nod].rson=v[past].rson;
                update(v[nod].lson,v[past].lson,st,mij,poz);
            }
            else{
                v[nod].lson=v[past].lson;
                v[nod].rson=++total;
                update(v[nod].rson,v[past].rson,mij+1,dr,poz);
            }
            v[nod].cnt=v[v[nod].lson].cnt+v[v[nod].rson].cnt;
            v[nod].sum=v[v[nod].lson].sum+v[v[nod].rson].sum;
        }
    }
    long long get_sum(int nod1,int nod2,int st,int dr,int k){
        if(st==dr)
            return 1LL*k*st;
        int mij=(st+dr)/2;
        int dreapta=v[v[nod1].rson].cnt-v[v[nod2].rson].cnt;
        if(dreapta>=k)
            return get_sum(v[nod1].rson,v[nod2].rson,mij+1,dr,k);
        return v[v[nod1].rson].sum-v[v[nod2].rson].sum+get_sum(v[nod1].lson,v[nod2].lson,st,mij,k-dreapta);
    }
}aint;

void dei(int l,int r,int optl,int optr,int start,int d){
    if(l>r)
        return;
    int optIndex=0;
    long long optAns=-1;
    int i;
    int mij=(l+r)/2;
    for(i=optl;i<=optr;++i){
        int drum1=start-mij;
        int drum2=i-start;
        int drum=((drum1<drum2)?2*drum1+drum2:drum1+2*drum2);
        int k=d-drum;
        long long rasp=0;
        if(k>0)
            rasp=aint.get_sum(root[i+1],root[mij],0,INF,min(k,i-mij+1));
        if(rasp>optAns){
            optAns=rasp;
            optIndex=i;
        }
    }
    maxself(ans,optAns);
    dei(l,mij-1,optl,optIndex,start,d);
    dei(mij+1,r,optIndex,optr,start,d);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]){
    int i;
    for(i=0;i<n;++i){
        root[i+1]=++aint.total;
        aint.update(root[i+1],root[i],0,INF,attraction[i]);
    }
    dei(0,start,start,n-1,start,d);
    return ans;
}

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