oj.uz

Submission #590467

# Submission time Handle Problem Language Result Execution time Memory
590467 2022-07-06T01:30:48 Z georgievskiy Holiday (IOI14_holiday) C++17
100 / 100
 562 ms 10468 KB 
#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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 7680 KB Output is correct
2 Correct 314 ms 7752 KB Output is correct
3 Correct 440 ms 7732 KB Output is correct
4 Correct 315 ms 7700 KB Output is correct
5 Correct 562 ms 6740 KB Output is correct
6 Correct 181 ms 4172 KB Output is correct
7 Correct 291 ms 4032 KB Output is correct
8 Correct 361 ms 4236 KB Output is correct
9 Correct 146 ms 4580 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1052 KB Output is correct
2 Correct 9 ms 1096 KB Output is correct
3 Correct 9 ms 1108 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 8 ms 980 KB Output is correct
6 Correct 3 ms 840 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 2 ms 724 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 10468 KB Output is correct
2 Correct 507 ms 9088 KB Output is correct
3 Correct 87 ms 2904 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 832 KB Output is correct
8 Correct 518 ms 6908 KB Output is correct
9 Correct 534 ms 6968 KB Output is correct