Submission #732931

#	Time	Username	Problem	Language	Result	Execution time	Memory
732931		finn__	Holiday (IOI14_holiday)	C++17	0 / 100	84 ms	2292 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

constexpr size_t N = 100000, L = 1 << 17;

int64_t a[N], c[N], tree[2 * L][2];
size_t e = 0, f = 0, s, d, l;

void update(size_t i, int64_t x, int64_t y)
{
    i += L;
    tree[i][0] += x;
    tree[i][1] += y;
    while (i >>= 1)
    {
        tree[i][0] = tree[2 * i][0] + tree[2 * i + 1][0];
        tree[i][1] = tree[2 * i][1] + tree[2 * i + 1][1];
    }
}

int64_t kth_greatest_sum(int64_t k)
{
    int64_t x = 0, i = 1;
    while (i < L)
    {
        if (tree[2 * i + 1][1] > k)
            i = 2 * i + 1;
        else
            x += tree[2 * i + 1][0], k -= tree[2 * i + 1][1], i = 2 * i;
    }
    return x;
}

void adjust(size_t i, size_t j)
{
    while (e < i)
        update(lower_bound(c, c + l, a[e]) - c, -a[e], -1), ++e;
    while (e > i)
        --e, update(lower_bound(c, c + l, a[e]) - c, a[e], 1);
    while (f < j)
        ++f, update(lower_bound(c, c + l, a[f]) - c, a[f], 1);
    while (f > j)
        update(lower_bound(c, c + l, a[f]) - c, -a[f], -1), --f;
}

int64_t dnc(size_t a, size_t b, size_t u, size_t v)
{
    size_t mid = (a + b) / 2, opt_i = v;
    int64_t x = 0;
    for (size_t i = u; i <= v; ++i)
    {
        size_t const used = mid - i + min(mid - s, s - i);
        if (used < d)
        {
            adjust(i, mid);
            int64_t y = kth_greatest_sum(d - used);
            if (y > x)
                x = y, opt_i = i;
        }
    }
    if (a + 1 <= (a + b) / 2)
        x = max(x, dnc(a, (a + b) / 2 - 1, u, opt_i));
    if ((a + b) / 2 + 1 <= b)
        x = max(x, dnc((a + b) / 2 + 1, b, opt_i, v));
    return x;
}

long long int findMaxAttraction(int n, int start, int _d, int attraction[])
{
    s = start, d = _d;
    for (size_t i = 0; i < n; ++i)
        a[i] = attraction[i];
    memcpy(c, a, n * sizeof *a);
    sort(c, c + n);
    l = unique(c, c + n) - c;
    update(lower_bound(c, c + l, a[0]) - c, a[0], 1);
    return dnc(s, n - 1, 0, s);
}

Compilation message (stderr)

holiday.cpp: In function 'int64_t kth_greatest_sum(int64_t)':
holiday.cpp:24:14: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   24 |     while (i < L)
      |            ~~^~~
holiday.cpp: In function 'long long int findMaxAttraction(int, int, int, int*)':
holiday.cpp:71:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   71 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~

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