Submission #226749

#	Time	Username	Problem	Language	Result	Execution time	Memory
226749		urd05	휴가 (IOI14_holiday)	C++14	100 / 100	893 ms	53068 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

int root[100001];
int n;
int st;
int d;
int arr[100000];
vector<long long> press;
long long dp[100000];

struct Node {
    int cnt;
    long long sum;
    int l,r;
};

vector<Node> pst;

void init(int node=0,int nodel=0,int noder=n-1) {
    if (nodel==noder) {
        return;
    }
    int mid=(nodel+noder)/2;
    if (pst[node].l==-1) {
        pst[node].l=pst.size();
        pst.push_back({0,0,-1,-1});
    }
    init(pst[node].l,nodel,mid);
    if (pst[node].r==-1) {
        pst[node].r=pst.size();
        pst.push_back({0,0,-1,-1});
    }
    init(pst[node].r,mid+1,noder);
}

void add(int prev,int node,int pos,int nodel=0,int noder=n-1) {
    pst[node].cnt=pst[prev].cnt+1;
    pst[node].sum=pst[prev].sum+press[pos];
    if (nodel==noder) {
        return;
    }
    int mid=(nodel+noder)/2;
    if (pos<=mid) {
        pst[node].l=pst.size();
        pst.push_back({0,0,-1,-1});
        pst[node].r=pst[prev].r;
        add(pst[prev].l,pst[node].l,pos,nodel,mid);
    }
    else {
        pst[node].l=pst[prev].l;
        pst[node].r=pst.size();
        pst.push_back({0,0,-1,-1});
        add(pst[prev].r,pst[node].r,pos,mid+1,noder);
    }
}

long long findsum(int lnode,int rnode,int k,int nodel=0,int noder=n-1) {
    if (nodel==noder) {
        return press[nodel]*k;
    }
    int mid=(nodel+noder)/2;
    if (pst[pst[rnode].r].cnt-pst[pst[lnode].r].cnt>=k) {
        return findsum(pst[lnode].r,pst[rnode].r,k,mid+1,noder);
    }
    else {
        return pst[pst[rnode].r].sum-pst[pst[lnode].r].sum+findsum(pst[lnode].l,pst[rnode].l,k-(pst[pst[rnode].r].cnt-pst[pst[lnode].r].cnt),nodel,mid);
    }
}

long long getsum(int l,int r,int k) {
    if (k<=0) {
        return 0;
    }
    return findsum(root[l],root[r+1],min(pst[root[r+1]].cnt-pst[root[l]].cnt,k));
}

void getans_l(int l,int r,int al,int ar) {
    if (l>r) {
        return;
    }
    int mid=(l+r)/2;
    long long ret=-1e16;
    int opt=-1;
    for(int i=max(mid,al);i<=ar;i++) {
        long long val=getsum(mid,i,d+2*mid-i-st);
        if (val>ret) {
            ret=val;
            opt=i;
        }
    }
    dp[mid]=ret;
    getans_l(l,mid-1,al,opt);
    getans_l(mid+1,r,opt,ar);
}

void getans_r(int l,int r,int al,int ar) {
    if (l>r) {
        return;
    }
    int mid=(l+r)/2;
    long long ret=-1e16;
    int opt=-1;
    for(int i=al;i<=min(mid,ar);i++) {
        long long val=getsum(i,mid,d+st+i-2*mid);
        if (val>ret) {
            ret=val;
            opt=i;
        }
    }
    dp[mid]=ret;
    getans_r(l,mid-1,al,opt);
    getans_r(mid+1,r,opt,ar);
}

long long findMaxAttraction(int nn,int start,int dd,int at[]) {
    n=nn;
    st=start;
    d=dd;
    for(int i=0;i<n;i++) {
        arr[i]=at[i];
        press.push_back(arr[i]);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=0;i<n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
    }
    pst.push_back({0,0,-1,-1});
    init();
    for(int i=0;i<n;i++) {
        root[i+1]=pst.size();
        pst.push_back({0,0,-1,-1});
        add(root[i],root[i+1],arr[i]);
    }
    long long ret=0;
    long long sum=0;
    priority_queue<long long,vector<long long>,greater<long long>> pq;
    for(int i=st;i>=0;i--) {
        pq.push(arr[i]);
        sum+=arr[i];
        while ((int)pq.size()>d-st+i&&!pq.empty()) {
            sum-=pq.top();
            pq.pop();
        }
        ret=max(ret,sum);
    }
    while (!pq.empty()) {
        pq.pop();
    }
    sum=0;
    for(int i=st;i<n;i++) {
        pq.push(arr[i]);
        sum+=arr[i];
        while ((int)pq.size()>d-i+st&&!pq.empty()) {
            sum-=pq.top();
            pq.pop();
        }
        ret=max(ret,sum);
    }
    getans_l(0,st,0,n-1);
    for(int i=0;i<=st;i++) {
        ret=max(ret,dp[i]);
    }
    getans_r(st,n-1,0,n-1);
    for(int i=st;i<n;i++) {
        ret=max(ret,dp[i]);
    }
    return ret;
}

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