Submission #590457

#	Time	Username	Problem	Language	Result	Execution time	Memory
590457		georgievskiy	Holiday (IOI14_holiday)	C++17	0 / 100	3390 ms	5292 KiB

holiday

#pragma GCC optimize("O3")
//#pragma GCC target("avx2")

//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 1e5+10;
//const int N = 200;
ll s[4 * N];
int c[4 * N];

void turnOn(int v, int tl, int tr, int i, int val) {
    if (tl + 1 == tr) {
        c[v] = 1;
        s[v] = val;
        return;
    }
    int m = (tl + tr) / 2;
    if (i < m)
        turnOn(2 * v + 1, tl, m, i, val);
    else
        turnOn(2 * v + 2, m, tr, i, val);
    c[v] = c[2 * v + 1] + c[2 * v + 2], s[v] = s[2 * v + 1] + s[2 * v + 2];
}

void turnOff(int v, int tl, int tr, int i) {
    if (tl + 1 == tr) {
        c[v] = 0;
        s[v] = 0;
        return;
    }
    int m = (tl + tr) / 2;
    if (i < m)
        turnOff(2 * v + 1, tl, m, i);
    else
        turnOff(2 * v + 2, m, tr, i);
    c[v] = c[2 * v + 1] + c[2 * v + 2], s[v] = s[2 * v + 1] + s[2 * v + 2];
}

ll sum(int v, int tl, int tr, int k) {
    if (c[v] <= 0 || k <= 0)
        return 0;
    if (c[v] <= k)
        return s[v];
    int m = (tl + tr) / 2;
    return sum(2 * v + 1, tl, m, k) + sum(2 * v + 2, m, tr, k - c[2 * v + 1]);
}

int f[N], pos[N];

void countAll(int l, int r, int d_min, int d_max, int n, int a[]) {
    if (l > r || d_min > d_max) return;

    int d = (d_min + d_max) / 2;
    ll s = 0;
    f[d] = l;
    for (int i = l; i <= r && d - i > 0; i++) {
        turnOn(0, 0, n, pos[i], a[i]);
        ll _sum = sum(0, 0, n, d - i);
        if (_sum > s)
            s = _sum, f[d] = i;
    }
    for (int i = l; i <= r && d - i > 0; i++)
        turnOff(0, 0, n, pos[i]);
    countAll(l, f[d], d_min, d-1, n, a);
    for (int i = l; i <= f[d]; i++)
        turnOn(0, 0, n, pos[i], a[i]);
    countAll(f[d], r, d+1, d_max, n, a);
}


ll findMaxAttraction(int n, int start, int d, int a[]) {
    assert(start == 0);
    if (d == 0) return 0;
    vector<pair<int, int>> t(n);
    for(int i = 0; i < n; i++)
        t[i] = {a[i], i};
    sort(t.rbegin(), t.rend());
    for (int i = 0; i < n; i++)
        pos[t[i].second] = i;

    countAll(0, n - 1, 0, d, n, a);
    for (int i = 0; i <= f[d]; i++)
        turnOn(0, 0, n, pos[i], a[i]);
    ll ans = sum(0, 0, n, d - f[d]);
    return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53