oj.uz

Submission #167845

# Submission time Handle Problem Language Result Execution time Memory
167845 2019-12-10T13:40:38 Z dolphingarlic Holiday (IOI14_holiday) C++14
100 / 100
 1004 ms 6904 KB 
#include "holiday.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

ll ans = 0;
int n, s, d, loc[100001], ptr;
pair<int, int> a[100001];

pair<ll, int> segtree[400001];
void add_city(int pos, bool inserting, int node = 1, int l = 1, int r = n) {
    if (l == r) {
        if (inserting) segtree[node] = {a[pos].first, 1};
        else segtree[node] = {0, 0};
    } else {
        int mid = (l + r) >> 1;
        if (pos > mid) add_city(pos, inserting, node * 2 + 1, mid + 1, r);
        else add_city(pos, inserting, node * 2, l, mid);
        segtree[node] = {segtree[node * 2].first + segtree[node * 2 + 1].first,
                         segtree[node * 2].second + segtree[node * 2 + 1].second};
    }
}
ll k_best(int k, int node = 1, int l = 1, int r = n) {
    if (k <= 0) return 0;
    if (segtree[node].second <= k) return segtree[node].first;
    int mid = (l + r) >> 1;
    if (segtree[node * 2].second >= k) return k_best(k, node * 2, l, mid);
    return segtree[node * 2].first + k_best(k - segtree[node * 2].second, node * 2 + 1, mid + 1, r);
}

void solve(int l, int r, int lopt, int ropt) {
    if (l > r) return;

    int mid = (l + r) >> 1;
    pair<ll, int> best = {LLONG_MIN, -1};

    // Update range
    if (mid < ptr) FOR(i, mid, ptr) add_city(loc[i], true);
    else FOR(i, ptr, mid) add_city(loc[i], false);
    ptr = mid;

    // D&C to find opt
    FOR(i, lopt, ropt + 1) {
        add_city(loc[i], true);
        best = max(best, {k_best(d + 2 * mid - s - i), -i});
    }

    ans = max(ans, best.first);
    int opt = -best.second;

    // Recursively solve left and right
    FOR(i, opt, ropt + 1) add_city(loc[i], false);
    solve(mid + 1, r, opt, ropt);
    FOR(i, lopt, opt) add_city(loc[i], false);
    solve(l, mid - 1, lopt, opt);
}

ll findMaxAttraction(int N, int S, int D, int A[]) {
    n = N, s = S + 1, d = D;
    FOR(i, 1, n + 1) a[i] = {A[i - 1], i};
    sort(a + 1, a + n + 1, greater<pair<int, int>>());
    FOR(i, 1, n + 1) loc[a[i].second] = i;

    ptr = s + 1;
    solve(1, s, s, n);

    // Reverse the whole thing
    FOR(i, 1, n + 1) {
        loc[n - a[i].second + 1] = i;
        add_city(i, false);
    }
    s = n - s + 1;

    ptr = s + 1;
    solve(1, s, s, n);

    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 6012 KB Output is correct
2 Correct 208 ms 6136 KB Output is correct
3 Correct 209 ms 6264 KB Output is correct
4 Correct 207 ms 6220 KB Output is correct
5 Correct 244 ms 6264 KB Output is correct
6 Correct 59 ms 1912 KB Output is correct
7 Correct 123 ms 3376 KB Output is correct
8 Correct 153 ms 3576 KB Output is correct
9 Correct 41 ms 1788 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 504 KB Output is correct
2 Correct 6 ms 504 KB Output is correct
3 Correct 6 ms 504 KB Output is correct
4 Correct 13 ms 504 KB Output is correct
5 Correct 12 ms 632 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 6036 KB Output is correct
2 Correct 217 ms 6776 KB Output is correct
3 Correct 326 ms 3448 KB Output is correct
4 Correct 13 ms 504 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 946 ms 6904 KB Output is correct
9 Correct 1004 ms 6868 KB Output is correct