oj.uz

Submission #241193

# Submission time Handle Problem Language Result Execution time Memory
241193 2020-06-23T09:05:27 Z Nightlight Holiday (IOI14_holiday) C++14
100 / 100
 844 ms 40696 KB 
#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.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 5 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 31 ms 5624 KB Output is correct
2 Correct 28 ms 5632 KB Output is correct
3 Correct 32 ms 7680 KB Output is correct
4 Correct 31 ms 7552 KB Output is correct
5 Correct 76 ms 17400 KB Output is correct
6 Correct 25 ms 5632 KB Output is correct
7 Correct 44 ms 9848 KB Output is correct
8 Correct 50 ms 11896 KB Output is correct
9 Correct 19 ms 4096 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1280 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 8 ms 1280 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 9 ms 1152 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 6 ms 512 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 6264 KB Output is correct
2 Correct 321 ms 40696 KB Output is correct
3 Correct 134 ms 17400 KB Output is correct
4 Correct 10 ms 1152 KB Output is correct
5 Correct 6 ms 640 KB Output is correct
6 Correct 7 ms 640 KB Output is correct
7 Correct 6 ms 640 KB Output is correct
8 Correct 844 ms 40072 KB Output is correct
9 Correct 778 ms 40184 KB Output is correct