Submission #282727

#	Time	Username	Problem	Language	Result	Execution time	Memory
282727		SamAnd	Holiday (IOI14_holiday)	C++17	100 / 100	543 ms	48340 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005, L = 20;

int start;
int n;
int a[N];

int z;
ll s[N * L];
int q[N * L];
int ul[N * L], ur[N * L];
int py[N * L];

int ubd(int tl, int tr, int x, int y, int pos)
{
    int ypos = ++z;
    ul[ypos] = ul[pos];
    ur[ypos] = ur[pos];
    s[ypos] = s[pos] + y;
    q[ypos] = q[pos] + 1;
    if (tl == tr)
    {
        py[ypos] = y;
        return ypos;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ul[ypos] = ubd(tl, m, x, y, ul[pos]);
    else
        ur[ypos] = ubd(m + 1, tr, x, y, ur[pos]);
    return ypos;
}

ll qry(int tl, int tr, int qq, int pos)
{
    if (pos == 0)
        return 0;
    if (qq >= q[pos])
        return s[pos];
    if (tl == tr)
        return qq * 1LL * py[pos];
    int m = (tl + tr) / 2;
    if (q[ur[pos]] >= qq)
        return qry(m + 1, tr, qq, ur[pos]);
    return qry(tl, m, qq - q[ur[pos]], ul[pos]) + s[ur[pos]];
}

int root[N];

ll ansr[N * 3];
void bilr(int l, int r, int opl, int opr, int qa)
{
    if (l > r)
        return;
    int m = (l + r) / 2;
    ll maxu = 0;
    int maxi;
    for (int i = opl; i <= opr; ++i)
    {
        if (m - (i - start) * qa >= 0)
        {
            ll u = qry(0, n - 1, m - (i - start) * qa, root[i]);
            if (u >= maxu)
            {
                maxu = u;
                maxi = i;
            }
        }
    }
    ansr[m] = maxu;
    bilr(l, m - 1, opl, maxi, qa);
    bilr(m + 1, r, maxi, opr, qa);
}

ll ansl[N * 3];
void bill(int l, int r, int opl, int opr, int qa)
{
    if (l > r)
        return;
    int m = (l + r) / 2;
    ll maxu = 0;
    int maxi;
    for (int i = opr; i >= opl; --i)
    {
        if (m - (start - i) * qa >= 0)
        {
            ll u = qry(0, n - 1, m - (start - i) * qa, root[i]);
            if (u >= maxu)
            {
                maxu = u;
                maxi = i;
            }
        }
    }
    ansl[m] = maxu;
    bill(m + 1, r, opl, maxi, qa);
    bill(l, m - 1, maxi, opr, qa);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    ::start = start;
    ::n = n;
    for (int i = 0; i < n; ++i)
    {
        a[i] = attraction[i];
    }

    ll ans = 0;

    vector<int> v;
    for (int i = 0; i < n; ++i)
        v.push_back(a[i]);
    sort(all(v));

    z = 0;
    root[start] = 0;
    for (int i = start + 1; i < n; ++i)
        root[i] = ubd(0, n - 1, lower_bound(all(v), a[i]) - v.begin(), a[i], root[i - 1]);
    bilr(0, d, start, n - 1, 1);

    z = 0;
    root[start] = ubd(0, n - 1, lower_bound(all(v), a[start]) - v.begin(), a[start], 0);
    for (int i = start - 1; i >= 0; --i)
        root[i] = ubd(0, n - 1, lower_bound(all(v), a[i]) - v.begin(), a[i], root[i + 1]);
    bill(0, d, 0, start, 2);

    for (int i = 0; i <= d; ++i)
        ans = max(ans, ansl[i] + ansr[d - i]);

    ////////////////////////////////////////////////////

    z = 0;
    root[start] = ubd(0, n - 1, lower_bound(all(v), a[start]) - v.begin(), a[start], 0);
    for (int i = start + 1; i < n; ++i)
        root[i] = ubd(0, n - 1, lower_bound(all(v), a[i]) - v.begin(), a[i], root[i - 1]);
    bilr(0, d, start, n - 1, 2);

    z = 0;
    root[start] = 0;
    for (int i = start - 1; i >= 0; --i)
        root[i] = ubd(0, n - 1, lower_bound(all(v), a[i]) - v.begin(), a[i], root[i + 1]);
    bill(0, d, 0, start, 1);

    for (int i = 0; i <= d; ++i)
        ans = max(ans, ansl[i] + ansr[d - i]);
    return ans;
}

Compilation message (stderr)

holiday.cpp: In function 'void bilr(int, int, int, int, int)':
holiday.cpp:79:9: warning: 'maxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
   79 |     bilr(l, m - 1, opl, maxi, qa);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
holiday.cpp: In function 'void bill(int, int, int, int, int)':
holiday.cpp:104:9: warning: 'maxi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  104 |     bill(m + 1, r, opl, maxi, qa);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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