Submission #779006

#	Time	Username	Problem	Language	Result	Execution time	Memory
779006		PoonYaPat	Holiday (IOI14_holiday)	C++14	24 / 100	66 ms	65536 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

int n,st,d,p[100001];
ll dpL[250005][3],dpR[250005][3],val[100001];
bool visL[250005][3],visR[250005][3];
vector<pii> v;

struct node {
    ll sum,cnt;
    node *l,*r;

    node(ll s, ll c) : sum(s), cnt(c), l(NULL), r(NULL) {}
    node(node *a, node *b) : sum(0), cnt(0), l(a), r(b) {
        sum=a->sum+b->sum;
        cnt=a->cnt+b->cnt;
    }
};
vector<node*> arrR,arrL;

node* build(int l, int r) {
    if (l==r) return new node(0ll,0ll);
    else {
        int mid=(l+r)/2;
        return new node(build(l,mid),build(mid+1,r));
    }
}

node* update(int l, int r, int x, ll val, node* pnode) {
    if (x>r || x<l) return pnode;
    if (l==r) return new node(val,1);
    int mid=(l+r)/2;
    return new node(update(l,mid,x,val,pnode->l),update(mid+1,r,x,val,pnode->r));
}

ll query(int l, int r, int want, node* pnode) {
    if (want==0) return 0;
    if (l==r) return pnode->sum;
    int mid=(l+r)/2;
    if (pnode->l->cnt<=want) return pnode->l->sum+query(mid+1,r,want-pnode->l->cnt,pnode->r);
    else return query(l,mid,want,pnode->l);
}

void findR(int ld, int rd, int l, int r, int w) {
    int day=(ld+rd)/2;
    if (visR[day][w]) return;
    visR[day][w]=true;

    int best=st;
    for (int i=l; i<=r; ++i) {
        int tour=day-(i-st)*w;
        if (tour<=0) continue;

        ll h=query(0,n-1,tour,arrR[i-st]);
        if (h>dpR[day][w]) {
            dpR[day][w]=h;
            best=i;
        }
    }
    
    if (ld<=rd) {
        findR(ld,day-1,l,best,w);
        findR(day+1,rd,best,r,w);
    }
}

void findL(int ld, int rd, int l, int r, int w) {
    int day=(ld+rd)/2;
    if (visL[day][w]) return;
    visL[day][w]=true;

    int best=st;
    for (int i=l; i<=r; ++i) {
        int tour=day-(st-i)*w;
        if (tour<=0) continue;

        ll h=query(0,n-1,tour,arrL[st-i]);
        if (h>dpL[day][w]) {
            dpL[day][w]=h;
            best=i;
        }
    }
    
    if (ld<=rd) {
        findL(ld,day-1,best,r,w);
        findL(day+1,rd,l,best,w);
    }
}

ll findMaxAttraction(int N, int start, int D, int att[]) {
    n=N; st=start; d=D;
    for (int i=0; i<n; ++i) val[i]=att[i], v.push_back(pii(att[i],i));
    sort(v.begin(),v.end(),greater<pii>());
    for (int i=0; i<n; ++i) p[v[i].second]=i;

    arrR.push_back(build(0,n-1));
    arrL.push_back(build(0,n-1));

    for (int i=st+1; i<n; ++i) arrR.push_back(update(0,n-1,p[i],val[i],arrR.back()));
    for (int i=st-1; i>=0; --i) arrL.push_back(update(0,n-1,p[i],val[i],arrL.back()));

    findR(0,d,st+1,n-1,1);
    findR(0,d,st+1,n-1,2);
    findL(0,d,0,st-1,1);
    findL(0,d,0,st-1,2);

    ll ans=0;
    for (int i=0; i<=d; ++i) { //go right for i days

        //go right first
        ans=max(ans,dpR[i][2]+dpL[d-i][1]);
        if (i!=d) ans=max(ans,dpR[i][2]+dpL[d-i-1][1]+val[st]);

        //go left first
        ans=max(ans,dpL[d-i][2]+dpR[i][1]);
        if (i!=d) ans=max(ans,dpL[d-i-1][2]+dpR[i][1]+val[st]);
        
    }

    return ans;
}

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