Submission #1286708

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286708		huyjavalt	Holiday (IOI14_holiday)	C++20	0 / 100	26 ms	4536 KiB

holiday

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

long long dp[2][100005];
int pos[2][100005];

int a[100005];
int curl = 1, curr = 0;
vector<long long> com;

struct Node{
    long long sum = 0;
    int cnt = 0;
}t[400005];

void update(int v, int tl, int tr, int pos, int x){
    if(tl == tr){
        t[v].cnt += x;
        t[v].sum += x*(com[tl-1]);
    }else{
        int tm = (tl+tr)/2;
        if(pos <= tm) update(v*2,tl,tm,pos,x);
        else update(v*2+1,tm+1,tr,pos,x);
        t[v].cnt = t[v*2].cnt + t[v*2+1].cnt;
        t[v].sum = t[v*2].sum + t[v*2+1].sum;
    }
}

long long walk(int v, int tl, int tr, int k){
    if(tl == tr) return min(k,t[v].cnt) * (com[tl-1]);
    int tm = (tl+tr)/2;
    if(k >= t[v*2+1].cnt) return walk(v*2,tl,tm,k-t[v*2+1].cnt) + t[v*2+1].sum;
    return walk(v*2+1,tm+1,tr,k);
}

long long query(int l, int r, int k){
    while(curr < r) update(1,1,com.size(),a[++curr],1);
    while(curr > r) update(1,1,com.size(),a[curr--],-1);
    while(curl < l) update(1,1,com.size(),a[curl++],-1);
    while(curl > l) update(1,1,com.size(),a[--curl],1);
    return walk(1,1,com.size(),k);
}

void DnC(int a[], long long d[], int p[], int l, int r, int tl, int tr, int s){
    if(tl > tr) return;
    int tm = (tl+tr)/2;


    p[tm] = l;
    for(int i = l; i <= min(tm+s,r); i++){
        int val = query(s,i,tm-(i-s));
        if(d[tm] < val){
            d[tm] = val;
            p[tm] = i;
        }
    }

    //cout << tm << ' ' << l << ' ' << r << ' ' << query(s,l,tm) << ' ' << d[tm] << endl;

    DnC(a,d,p,l,p[tm],tl,tm-1,s);
    DnC(a,d,p,p[tm],r,tm+1,tr,s);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]){
    start++;
    for(int i = 1; i <= n; i++) com.push_back(attraction[i-1]);
    sort(com.begin(), com.end());
    com.erase(unique(com.begin(), com.end()), com.end());
    for(int i = 1; i <= n; i++) attraction[i-1] = lower_bound(com.begin(), com.end(), attraction[i-1]) - com.begin() + 1;

    for(int i = 1; i <= n; i++) a[i] = attraction[i-1];
    DnC(a,dp[0],pos[0],start+1,n,1,d,start+1);
    query(1,0,0);

    for(int i = 1; i <= n; i++){
        a[i] = attraction[n-i];
        //cout << a[i] << endl;
    }
    DnC(a,dp[1],pos[1],n-start+2,n,1,d,n-start+2);

    for(int i = 1; i <= n; i++) a[i] = attraction[i-1];
    long long ans = max(com[a[start]-1], dp[1][d-1]);
    if(d >= 2) ans = max(ans,dp[1][d-2] + com[a[start]-1]);
    //for(int i = 1; i <= d; i++) cout << dp[0][i] << ' ' << dp[1][i] << endl;

    for(int i = 1; i <= d; i++){ //days used going right
        if(d-i-(pos[0][i-1] - start)-1 > 0) ans = max(ans, dp[0][i-1] + dp[1][d-i-(pos[0][i-1] - start)-1]);
        if(d-i-(pos[0][i-1] - start)-2 > 0) ans = max(ans, dp[0][i-1] + dp[1][d-i-(pos[0][i-1] - start)-2]+com[a[start]-1]);
    }

    return ans;
}

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