oj.uz

Submission #282727

# Submission time Handle Problem Language Result Execution time Memory
282727 2020-08-24T19:37:21 Z SamAnd Holiday (IOI14_holiday) C++17
100 / 100
 543 ms 48340 KB 
#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

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.0 / 7.0

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

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 47472 KB Output is correct
2 Correct 226 ms 47472 KB Output is correct
3 Correct 261 ms 47472 KB Output is correct
4 Correct 243 ms 47472 KB Output is correct
5 Correct 264 ms 41648 KB Output is correct
6 Correct 91 ms 14200 KB Output is correct
7 Correct 142 ms 22640 KB Output is correct
8 Correct 164 ms 27372 KB Output is correct
9 Correct 64 ms 11772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1408 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 6 ms 1408 KB Output is correct
4 Correct 7 ms 1152 KB Output is correct
5 Correct 8 ms 1024 KB Output is correct
6 Correct 3 ms 640 KB Output is correct
7 Correct 2 ms 640 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 48268 KB Output is correct
2 Correct 543 ms 48340 KB Output is correct
3 Correct 103 ms 13936 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct
5 Correct 2 ms 544 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 452 ms 24560 KB Output is correct
9 Correct 478 ms 24560 KB Output is correct