oj.uz

Submission #986395

# Submission time Handle Problem Language Result Execution time Memory
986395 2024-05-20T12:43:58 Z Sharky Holiday (IOI14_holiday) C++17
100 / 100
 1238 ms 27696 KB 
#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;

using i32 = int32_t;
#define int long long

const int N = 200005;

int pos[N], a[N], dist, _n;

struct segtree {
    int size = 1;
    vector<pair<int, int>> seg;
    void init(int n) {
        while (size < n) size *= 2;
        seg.assign(2 * size + 5, {0, 0});
    }
    void update(int posi, int val, int l, int r, int id, bool add) {
        // cout << posi << ' ' << val << ' ' << l << ' ' << r << ' ' << id << ' ' << add << '\n';
        if (l == r) {
            if (add) {
                seg[id].first = 1;
                seg[id].second = val;
            } else {
                seg[id].first = seg[id].second = 0;
            }
            return;
        }
        int mid = (l + r) / 2;
        if (posi <= mid) update(posi, val, l, mid, id * 2, add);
        else update(posi, val, mid + 1, r, id * 2 + 1, add);
        seg[id].first = seg[id * 2].first + seg[id * 2 + 1].first;
        seg[id].second = seg[id * 2].second + seg[id * 2 + 1].second;
    }
    int query(int k, int l, int r, int id) {
        if (k <= 0) return 0;
        if (l == r) return seg[id].second;
        if (seg[id].first < k) return seg[id].second;
        int mid = (l + r) / 2;
        if (k >= seg[id * 2 + 1].first) {
            return seg[id * 2 + 1].second + query(k - seg[id * 2 + 1].first, l, mid, id * 2);
        }
        return query(k, mid + 1, r, id * 2 + 1);
    }
} st;

void dnc(int l, int r, int optl, int optr, vector<int>& f) {
    if (l > r) {
        for (int i = optl; i <= optr; i++) st.update(pos[i], a[i], 1, _n, 1, 1);
        return;
    }
    int bst = -1, opt = 0, mid = (l + r) / 2;
    for (int i = optl; i <= optr; i++) {
        // cout << "update: " << pos[i] << ' ' << a[i] << ' ' << 1 << ' ' << _n << ' ' << 1 << '\n';
        st.update(pos[i], a[i], 1, _n, 1, 1);
        // cout << "query: " << mid - (i - 1) << ' ' << 1 << ' ' << _n << ' ' << 1 << '\n';
        int cur = st.query(mid - (i - 1), 1, _n, 1);
        if (cur > bst) bst = cur, opt = i;
    }
    f[mid] = bst;
    // cout << mid << ' ' << opt << ' ' << bst << '\n';
    for (int i = optl; i <= optr; i++) st.update(pos[i], a[i], 1, _n, 1, 0);
    dnc(l, mid - 1, optl, opt, f);
    st.update(pos[opt], a[opt], 1, _n, 1, 0);
    dnc(mid + 1, r, opt, optr, f);
}

vector<int> solve(vector<int> vt) {
    int n = vt.size() - 1;
    _n = n;
    for (int i = 1; i <= n; i++) a[i] = vt[i];
    st.init(n + 1);
    vector<pair<int, int>> cities = {{0, 0}};
    for (int i = 1; i <= n; i++) cities.push_back({a[i], i});
    sort(cities.begin() + 1, cities.end());
    for (int i = 1; i <= n; i++) pos[cities[i].second] = i;
    vector<int> f(dist+1, 0);
    dnc(1, dist, 1, n, f);
    return f;
}

int findMaxAttraction(i32 n, i32 start, i32 d, i32 attraction[]) {
    if (d == 0) return 0;
    // if (d == 1) return attraction[start];
    dist = d;
    vector<int> vt = {0};
    for (int i = start; i < n; i++) vt.push_back(attraction[i]);
    vector<int> f = solve(vt);
    vt = {0};
    vt.push_back(0);
    for (int i = start - 1; i >= 0; i--) {
        vt.push_back(0);
        vt.push_back(attraction[i]);
    }
    vector<int> g = solve(vt);
    int ans = 0;
    for (int i = 0; i <= d; i++) ans = max(ans, f[i] + g[d - i]);
    vt = {0};
    for (int i = start; i >= 0; i--) vt.push_back(attraction[i]);
    f = solve(vt);
    vt = {0};
    vt.push_back(0);
    for (int i = start + 1; i < n; i++) {
        vt.push_back(0);
        vt.push_back(attraction[i]);
    }
    g = solve(vt);
    for (int i = 0; i <= d; i++) ans = max(ans, f[i] + g[d - i]);
    return ans;
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1136 ms 25796 KB Output is correct
2 Correct 1045 ms 26860 KB Output is correct
3 Correct 1145 ms 25836 KB Output is correct
4 Correct 1033 ms 26340 KB Output is correct
5 Correct 1164 ms 24692 KB Output is correct
6 Correct 422 ms 12440 KB Output is correct
7 Correct 614 ms 14084 KB Output is correct
8 Correct 732 ms 14880 KB Output is correct
9 Correct 320 ms 13040 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 3580 KB Output is correct
2 Correct 25 ms 3580 KB Output is correct
3 Correct 22 ms 3616 KB Output is correct
4 Correct 20 ms 3416 KB Output is correct
5 Correct 18 ms 3164 KB Output is correct
6 Correct 6 ms 2904 KB Output is correct
7 Correct 5 ms 2968 KB Output is correct
8 Correct 5 ms 2904 KB Output is correct
9 Correct 5 ms 2908 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1163 ms 23116 KB Output is correct
2 Correct 1238 ms 27696 KB Output is correct
3 Correct 405 ms 8048 KB Output is correct
4 Correct 16 ms 3164 KB Output is correct
5 Correct 5 ms 2908 KB Output is correct
6 Correct 5 ms 2908 KB Output is correct
7 Correct 6 ms 3048 KB Output is correct
8 Correct 1157 ms 14176 KB Output is correct
9 Correct 1169 ms 14176 KB Output is correct