Submission #241193

#	Time	Username	Problem	Language	Result	Execution time	Memory
241193		Nightlight	Holiday (IOI14_holiday)	C++14	100 / 100	844 ms	40696 KiB

holiday

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

int idx;
long long val[100005];
long long A[100005];
int N, S, D, sz;
long long dp[100005];

//persistent segtree part
int root[100005];
int cnt[2000005], L[2000005], R[2000005];
long long sum[2000005];

int build(int l, int r) {
    int now = ++idx;
    if(l == r) return now;
    int mid = (l + r) >> 1;
    L[now] = build(l, mid);
    R[now] = build(mid + 1, r);
    return now;
}

int update(int last, int pos, int l, int r) {
    int now = ++idx;
    L[now] = L[last];
    R[now] = R[last];
    cnt[now] = cnt[last] + 1;
    sum[now] = sum[last] + val[pos];
    if(l == r) return now;

    int mid = (l + r) >> 1;
    if(pos <= mid) L[now] = update(L[last], pos, l, mid);
    else R[now] = update(R[last], pos, mid + 1, r);
    return now;
}

long long query(int kl, int kr, int k, int l, int r) {
    if(l == r) return val[l] * k;
    int mid = (l + r) >> 1;
    int now = cnt[R[kr]] - cnt[R[kl]]; 
    if(k <= now) {
        return query(R[kl], R[kr], k, mid + 1, r);
    }else {
        return sum[R[kr]] - sum[R[kl]] + query(L[kl], L[kr], k - now, l, mid);
    }
}

long long cost(int l, int r, int day) {
    if(day <= 0) return 0;
    return query(root[l - 1], root[r], min(day, r - l + 1), 1, sz);
}
//dnc cari t4 belok optimal
//kanan ke kiri
void dncL(int l, int r, int kl, int kr) {
    if(l > r) return;
    long long best = -1;
    int id = -1, mid = (l + r) >> 1;
    for(int i = kl; i <= kr && i <= mid; i++) {
        long long now = cost(i, mid, D - ((mid - S) + (mid - i)));
        if(now > best) {
            best = now;
            id = i;
        }
    }
    dp[mid] = best;
    dncL(l, mid - 1, kl, id);
    dncL(mid + 1, r, id, kr);
}

//kiri ke kanan
void dncR(int l, int r, int kl, int kr) {
    if(l > r) return;
    long long best = -1;
    int id = -1, mid = (l + r) >> 1;
    for(int i = max(mid, kl); i <= kr; i++) {
        long long now = cost(mid, i, D - ((S - mid) + (i - mid)));
        if(now > best) {
            best = now;
            id = i;
        }
    }
    dp[mid] = best;
    dncR(l, mid - 1, kl, id);
    dncR(mid + 1, r, id, kr);
}

void prepare() {
    sort(val + 1, val + N + 1);
    sz = unique(val + 1, val + N + 1) - val - 1;
    for(int i = 1; i <= N; i++) {
        A[i] = lower_bound(val + 1, val + sz + 1, A[i]) - val;
//        cout << A[i] << " ";
    }
//    cout << "\n";
    root[0] = build(1, sz);
    for(int i = 1; i <= N; i++) {
        root[i] = update(root[i - 1], A[i], 1, sz);
    }
/*    int ty, l, r, ak;
    while(1) {
        cin >> ty;
        if(!ty) break;
        cin >> l >> r >> ak;
        cout << cost(l, r, ak) << "\n";
    }*/
}

long long int findMaxAttraction(int n, int start, int d, int aa[]) {
    N = n, S = start + 1, D = d;
    for(int i = 1; i <= N; i++) {
        A[i] = aa[i - 1];
        val[i] = aa[i - 1];
    }
    prepare();
    long long ans = 0;
    dncL(S, N, 1, N);
    for(int i = 1; i <= N; i++) {
        ans = max(ans, dp[i]);
    }
    dncR(1, S, 1, N);
    for(int i = 1; i <= N; i++) {
        ans = max(ans, dp[i]);
    }
    return ans;
}

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