oj.uz

Submission #226749

# Submission time Handle Problem Language Result Execution time Memory
226749 2020-04-25T06:35:52 Z urd05 Holiday (IOI14_holiday) C++14
100 / 100
 893 ms 53068 KB 
#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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 52264 KB Output is correct
2 Correct 301 ms 52260 KB Output is correct
3 Correct 281 ms 52296 KB Output is correct
4 Correct 264 ms 52272 KB Output is correct
5 Correct 246 ms 52264 KB Output is correct
6 Correct 67 ms 13524 KB Output is correct
7 Correct 132 ms 26460 KB Output is correct
8 Correct 178 ms 51376 KB Output is correct
9 Correct 58 ms 13280 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2192 KB Output is correct
2 Correct 10 ms 2192 KB Output is correct
3 Correct 10 ms 2192 KB Output is correct
4 Correct 12 ms 2192 KB Output is correct
5 Correct 12 ms 2064 KB Output is correct
6 Correct 6 ms 836 KB Output is correct
7 Correct 8 ms 836 KB Output is correct
8 Correct 7 ms 836 KB Output is correct
9 Correct 6 ms 836 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 53040 KB Output is correct
2 Correct 401 ms 53068 KB Output is correct
3 Correct 202 ms 26580 KB Output is correct
4 Correct 12 ms 2192 KB Output is correct
5 Correct 6 ms 836 KB Output is correct
6 Correct 7 ms 836 KB Output is correct
7 Correct 6 ms 836 KB Output is correct
8 Correct 739 ms 52936 KB Output is correct
9 Correct 893 ms 52900 KB Output is correct