oj.uz

Submission #564395

# Submission time Handle Problem Language Result Execution time Memory
564395 2022-05-19T05:53:42 Z thecodingwizard Holiday (IOI14_holiday) C++17
100 / 100
 1664 ms 16616 KB 
#include <bits/stdc++.h>
#include "holiday.h"

using namespace std;
using ll = long long;

#define f first
#define s second
#define ii pair<int, int>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

const int maxn = 100000;
int n, start, d;

int stIndex[maxn];
struct node {
    ll val;
    int initVal;
    int ct;
} st[maxn*4];

void buildST(int attraction[]) {
    vector<ii> attractions;
    for (int i = 0; i < n; i++) {
        attractions.pb(mp(attraction[i], i));
    }
    sort(all(attractions));
    reverse(all(attractions));
    int i = 0;
    for (auto x : attractions) {
        stIndex[x.s] = i;
        i++;
    }
    auto build = [&](int p, int i, int j, const auto &build)->void {
        if (i == j) {
            st[p] = node{0, attractions[i].f, 0};
        } else {
            build(p*2, i, (i+j)/2, build);
            build(p*2+1, (i+j)/2+1, j, build);
            st[p] = node{0,-1,0};
        }
    };
    build(1, 0, n-1, build);
}

void upd(int p, int i, int j, int k, bool isActive) {
    if (i > k || j < k) return;
    if (i == j && i == k) {
        st[p].val = isActive ? st[p].initVal : 0;
        st[p].ct = isActive;
    } else {
        upd(p*2, i, (i+j)/2, k, isActive);
        upd(p*2+1, (i+j)/2+1, j, k, isActive);
        st[p].val = st[p*2].val + st[p*2+1].val;
        st[p].ct = st[p*2].ct + st[p*2+1].ct;
    }
}

ll qry(int p, int i, int j, int k) {
    if (st[p].ct <= k) return st[p].val;
    if (i == j) return k <= 0 ? 0 : st[p].val;
    if (st[p*2].ct >= k) return qry(p*2, i, (i+j)/2, k);
    return st[p*2].val + qry(p*2+1, (i+j)/2+1, j, k - st[p*2].ct);
}

vector<ll> oneWayLeft(3*maxn), oneWayRight(3*maxn);
vector<ll> twoWayLeft(3*maxn), twoWayRight(3*maxn);

void compute(int l, int r, int optl, int optr, vector<ll> &dp, int isTwoWay = 0) {
    if (l > r) return;

    int mid = (l+r)/2;
    ll best = -1; int bestTransition = -1;
    for (int k = optl; k <= optr; k++) {
        upd(1, 0, n-1, stIndex[k], 1);
        int stepsRemaining = mid - (k - start) * (isTwoWay ? 2 : 1);

        ll val = qry(1, 0, n-1, stepsRemaining);
        if (best < val) {
            best = val;
            bestTransition = k;
        }
    }

    dp[mid] = best;

    for (int k = bestTransition+1; k <= optr; k++) {
        upd(1, 0, n-1, stIndex[k], 0);
    }
    compute(mid+1, r, bestTransition, optr, dp, isTwoWay);

    for (int k = optl; k <= bestTransition; k++) {
        upd(1, 0, n-1, stIndex[k], 0);
    }
    compute(l, mid-1, optl, bestTransition, dp, isTwoWay);
}

long long int findMaxAttraction(int N, int Start, int D, int attraction[]) {
    n = N, start = Start, d = D;
    int backup = attraction[start];

    buildST(attraction);
    compute(0, d, start, n-1, oneWayRight);

    attraction[start] = 0;
    reverse(attraction, attraction+N);
    buildST(attraction);
    start = n - start - 1;
    compute(0, d, start, n-1, oneWayLeft);

    reverse(attraction, attraction+N);
    start = n - start - 1;
    attraction[start] = backup;
    buildST(attraction);
    compute(0, d, start, n-1, twoWayRight, 1);

    attraction[start] = 0;
    reverse(attraction, attraction+N);
    start = n - start - 1;
    buildST(attraction);
    compute(0, d, start, n-1, twoWayLeft, 1);

    ll best = 0;
    for (int x = 0; x <= d; x++) {
        best = max(best, max(oneWayRight[x] + twoWayLeft[d-x], twoWayRight[x] + oneWayLeft[d-x]));
    }

    return best;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 16384 KB Output is correct
2 Correct 1416 ms 16460 KB Output is correct
3 Correct 1406 ms 16388 KB Output is correct
4 Correct 1378 ms 16468 KB Output is correct
5 Correct 1558 ms 16264 KB Output is correct
6 Correct 618 ms 11652 KB Output is correct
7 Correct 876 ms 13236 KB Output is correct
8 Correct 966 ms 13316 KB Output is correct
9 Correct 526 ms 11676 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 10196 KB Output is correct
2 Correct 32 ms 10324 KB Output is correct
3 Correct 30 ms 10324 KB Output is correct
4 Correct 32 ms 10324 KB Output is correct
5 Correct 28 ms 10324 KB Output is correct
6 Correct 12 ms 10080 KB Output is correct
7 Correct 11 ms 10068 KB Output is correct
8 Correct 12 ms 10068 KB Output is correct
9 Correct 13 ms 10068 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1463 ms 16496 KB Output is correct
2 Correct 1664 ms 16396 KB Output is correct
3 Correct 586 ms 13140 KB Output is correct
4 Correct 28 ms 10196 KB Output is correct
5 Correct 10 ms 10068 KB Output is correct
6 Correct 9 ms 10068 KB Output is correct
7 Correct 10 ms 10096 KB Output is correct
8 Correct 1606 ms 16508 KB Output is correct
9 Correct 1505 ms 16616 KB Output is correct