oj.uz

Submission #467333

# Submission time Handle Problem Language Result Execution time Memory
467333 2021-08-22T16:21:30 Z apostoldaniel854 Holiday (IOI14_holiday) C++14
93 / 100
 1002 ms 8120 KB 
#include "holiday.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define dbg(x) cerr << #x << " " << x << "\n"

const int MAX_N = 1e5;

pair <int, int> a[1 + MAX_N];

class switch_max {
public:
    struct node_state {
        int cnt_on;
        ll sum;
    };
    vector <node_state> seg;
    int n;
    switch_max(int n) {
        this->n = n;
        seg.resize(1 + 4 * n, {0, 0});
    }
    node_state join(node_state L, node_state R) {
        node_state RES;
        RES.cnt_on = L.cnt_on + R.cnt_on;
        RES.sum = L.sum + R.sum;
        return RES;
    }
    void treat_leaf(int node, bool state, int value) {
        seg[node] = {state, value};
    };
    void change(int node, int lb, int rb, int pos, bool state, int value) {
        if (lb == rb) {
            treat_leaf(node, state, value);
            return;
        }
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (pos <= mid)
            change(lnode, lb, mid, pos, state, value);
        else
            change(rnode, mid + 1, rb, pos, state, value);
        seg[node] = join(seg[lnode], seg[rnode]);
    }
    ll solve(int node, int lb, int rb, int k) {
        if (seg[node].cnt_on <= k)
            return seg[node].sum;
        int mid = (lb + rb) / 2, lnode = node * 2, rnode = node * 2 + 1;
        if (seg[rnode].cnt_on >= k)
            return solve(rnode, mid + 1, rb, k);
        return seg[rnode].sum + solve(lnode, lb, mid, k - seg[rnode].cnt_on);
    }
    void turn_on(int pos) {
        change(1, 1, n, pos, true, a[pos].first);
    }
    void turn_off(int pos) {
        change(1, 1, n, pos, false, 0);
    }
    ll solve(int k) {
        return solve(1, 1, n, k);
    }
};

ll ans;
int mp[1 + MAX_N];
int pivot;
void divide(int lb, int rb, int bestl, int bestr, switch_max &solver, int d) {
    if (lb > rb || bestl > bestr)
        return;
    int mid = (lb + rb) / 2;
    for (int i = mid; i <= rb; i++)
        solver.turn_on(mp[i]);

    int bestmid = bestl;
    ll bestvalue = -1;
    for (int i = bestl; i <= bestr; i++) {
        int to_grab = d - (pivot - mid) - (i - mid);
        if (to_grab > 0) {
            solver.turn_on(mp[i]);
            ll cnt = solver.solve(to_grab);
            if (cnt > bestvalue) {
                bestvalue = cnt;
                bestmid = i;
            }
        }
    }
    ans = max(ans, bestvalue);
    for (int i = bestl + 1; i <= bestr; i++)
        solver.turn_off(mp[i]);
    divide(lb, mid - 1, bestl, bestmid, solver, d);
    for (int i = mid; i <= rb; i++)
        solver.turn_off(mp[i]);
    for (int i = bestl; i < bestmid; i++)
        solver.turn_on(mp[i]);
    divide(mid + 1, rb, bestmid, bestr, solver, d);
    for (int i = bestl; i < bestmid; i++)
        solver.turn_off(mp[i]);
}
/**
100 0 150
4 82 9 38 25 3 48 61 2 39 42 73 64 23 58 42 39 32 34 90 45 12 75 98 90 36 62 97 86 89 69 56 70 44 94 95 47 7 22 16 46 64 89 77 53 46 18 92 45 18 48 56 30 89 20 86 24 48 83 76 36 17 31 72 62 91 32 75 98 54 91 10 85 80 87 37 92 71 96 2 89 9 59 86 98 79 71 21 26 19 63 28 37 94 100 65 50 31 39 13


**/
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    start++;
    for (int i = 1; i <= n; i++)
        a[i] = {attraction[i - 1], i};
    sort (a + 1, a + n + 1);
    switch_max solver(n);
    for (int i = 1; i <= n; i++)
        mp[a[i].second] = i;
    pivot = start;
    divide(1, start, start, n, solver, d);
    for (int i = 1; i <= n; i++)
        mp[n - a[i].second + 1] = i;
    pivot = n - start + 1;
    divide(1, n - start + 1, n - start + 1, n, solver, d);
    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Incorrect 1 ms 588 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 8012 KB Output is correct
2 Correct 205 ms 8012 KB Output is correct
3 Correct 226 ms 8012 KB Output is correct
4 Correct 205 ms 8012 KB Output is correct
5 Correct 303 ms 7468 KB Output is correct
6 Correct 77 ms 2764 KB Output is correct
7 Correct 164 ms 4440 KB Output is correct
8 Correct 188 ms 5196 KB Output is correct
9 Correct 52 ms 2124 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 844 KB Output is correct
2 Correct 5 ms 844 KB Output is correct
3 Correct 5 ms 844 KB Output is correct
4 Correct 15 ms 844 KB Output is correct
5 Correct 13 ms 844 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 5 ms 716 KB Output is correct
9 Correct 4 ms 716 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 8100 KB Output is correct
2 Correct 223 ms 8120 KB Output is correct
3 Correct 272 ms 3916 KB Output is correct
4 Correct 11 ms 844 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 4 ms 716 KB Output is correct
7 Correct 4 ms 764 KB Output is correct
8 Correct 987 ms 7984 KB Output is correct
9 Correct 1002 ms 8104 KB Output is correct