Submission #362769

#	Time	Username	Problem	Language	Result	Execution time	Memory
362769		Lam_lai_cuoc_doi	휴가 (IOI14_holiday)	C++17	Compilation error	0 ms	0 KiB

holiday

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 2;
const ll Inf = 1e17;
int n, s, d;
int a[N], id[N], now[N];
ll dp[N];
struct node
{
    int v;
    ll sum;
    node()
    {
        v = sum = 0;
    }
    node(const node &a, const node &b)
    {
        v = a.v + b.v;
        sum = a.sum + b.sum;
    }
};
struct SegmentTree
{
    node st[N * 4];
    bool ck[N];
    SegmentTree()
    {
        memset(ck, 0, sizeof ck);
    }
    void Update(int id, int l, int r, int pos, ll v)
    {
        if (l > pos || r < pos)
            return;
        if (l == pos && l == r)
        {
            st[id].v ^= 1;
            st[id].sum += v;
            return;
        }
        Update(id << 1, l, (l + r) / 2, pos, v);
        Update(id << 1 | 1, (l + r) / 2 + 1, r, pos, v);
        st[id] = node(st[id << 1], st[id << 1 | 1]);
    }
    void Update(int v)
    {
        Update(1, 1, n, v, (ck[v] ? -1 : 1) * a[id[v]]);
        ck[v] ^= 1;
    }
    ll Get(int id, int l, int r, int d)
    {
        if (l == r)
            return st[id].sum;
        if (st[id << 1].v >= d)
            return Get(id << 1, l, (l + r) / 2, d);
        else
            return st[id << 1].sum + Get(id << 1 | 1, (l + r) / 2 + 1, r, d - st[id << 1].v);
    }
    ll Get(int d)
    {
        if (d == 0)
            return 0;
        return Get(1, 1, n, d);
    }
} f;

void DAC(int l, int r, int optl, int optr)
{
    if (l > r)
        return;
    if (optl == optr)
    {
        for (int i = optl; i < l; ++i)
            f.Update(now[i]);
        for (; l <= r; ++l)
        {
            f.Update(now[l]);
            dp[l] = f.Get(d - (l - s + l - optl));
        }
        for (int i = optl; i <= r; ++i)
            f.Update(now[i]);
        return;
    }
    int optmid(-1);
    int mid = (l + r) / 2;
    for (int i = optl; i <= mid; ++i)
        f.Update(now[i]);
    for (int i = optl; i <= optr; ++i)
    {
        ll v = f.Get(d - (mid - s + mid - i));
        if (dp[mid] < v)
        {
            dp[mid] = v;
            optmid = i;
        }
        f.Update(now[i]);
    }
    for (int i = optr + 1; i <= mid; ++i)
        f.Update(now[i]);
    DAC(l, mid - 1, optl, optmid);
    DAC(mid + 1, r, optmid, optr);
}

ll findMaxAttraction(int input1, int input2, int input3, int arr[])
{
    n = input1;
    s = ++input2;
    d = input3;
    for (int i = 1; i <= n; ++i)
        id[i] = i,
        a[i] = arr[i - 1];
    sort(id + 1, id + n + 1, [&](const int &x, const int &y) {
        return a[x] > a[y];
    });
    for (int i = 1; i <= n; ++i)
        now[id[i]] = i;
    fill_n(dp, N, -Inf);
    DAC(s, min(n, s + d - 1), 1, s - 1);
    ll ans(0);
    ans = max(ans, *max_element(dp + 1, dp + n + 1));
    fill_n(dp, N, -Inf);
    reverse(a + 1, a + n + 1);
    s = n - s + 1;
    DAC(s, min(n, s + d - 1), 1, s - 1);
    ans = max(ans, *max_element(dp + 1, dp + n + 1));
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    int a[N];
    cin >> n >> s >> d;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    cout << findMaxAttraction(n, s, d, a);
}

Compilation message (stderr)

/tmp/cc7EHSqq.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccanGeNw.o:holiday.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status