Submission #590467

#	Time	Username	Problem	Language	Result	Execution time	Memory
590467		georgievskiy	Holiday (IOI14_holiday)	C++17	100 / 100	562 ms	10468 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 = 1.1e5;
//const int N = 200;
struct solveHalf {

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[3*N], pos[N];
ll w[3*N];

void countAll(int l, int r, int d_min, int d_max, int n, signed 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;
    }
    w[d] = s;
    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);
}


void solve(signed n, signed start, signed d, signed a[]) {
    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);
}

}l, r;

int al[N], ar[N];

ll findMaxAttraction(signed n, signed start, signed d, signed a[]) {
    int p1 = 0;
    for (int i = start - 1; i >= 0; i--)
        al[p1++] = a[i];
    int p2 = 0;
    for (int i = start; i < n; i++)
        ar[p2++] = a[i];
    if (p1 == 0) {
        r.solve(p2, 0, d, ar);
        return r.w[d];
    }
    l.solve(p1, 0, d, al);
    r.solve(p2, 0, d, ar);
    ll ans = 0;
    for (int i = 0; i <= d; i++) {
        int j = d - i - r.f[i] - 1;
        ll _ans = r.w[i];
        if (j >= 0) _ans += l.w[j];
        ans = max(_ans, ans);
        //cout << i << ' ' << _ans << '\n';
    }
    for (int i = 0; i < d; i++) {
        int j = d - i - l.f[i] - 2;
        ll _ans = l.w[i];
        if (j >= 0) _ans += r.w[j];
        ans = max(_ans, ans);
        //cout << i << ' ' << _ans << '\n';
    }
    return ans;
}

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