Submission #1277228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277228		andrei_iorgulescu	휴가 (IOI14_holiday)	C++20	30 / 100	28 ms	4456 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

using integer = int;
#define int long long

struct AIB///init(valorile posibile); update(val, fr) -> pune fr aparitii de val; query(k) -> suma celor mai mari k din structura
{
    map<int, int> mp;
    vector<int> rvalue;
    int n;
    vector<int> aib1, aib2;///aib1 -> cate <= i, aib2 -> suma rvalue a lor

    void init(vector<int> values)
    {
        mp.clear();
        rvalue.clear();
        n = 0;
        aib1.clear();
        aib2.clear();
        int psn = 0;
        sort(values.begin(), values.end());
        for (auto it : values)
        {
            if (!mp[it])
            {
                psn++;
                mp[it] = psn;
            }
        }
        n = psn;
        aib1.resize(n + 1);
        aib2.resize(n + 1);
        rvalue.resize(n + 1);
        for (auto it : values)
            rvalue[mp[it]] = it;
    }

    int query1(int pos)
    {
        int rr = 0;
        for (int i = pos; i > 0; i -= (i & -i))
            rr += aib1[i];
        return rr;
    }

    int query2(int pos)
    {
        int rr = 0;
        for (int i = pos; i > 0; i -= (i & -i))
            rr += aib2[i];
        return rr;
    }

    void update(int val, int fr)
    {
        val = mp[val];
        for (int i = val; i <= n; i += (i & -i))
        {
            aib1[i] += fr;
            aib2[i] += fr * rvalue[val];
        }
    }

    int query(int k)
    {
        if (query1(n) <= k)
            return query2(n);
        if (k <= 0)
            return 0;
        int sm_tot = query2(n);
        int df = query1(n) - k;
        int st = 0, pas = 1 << 18;
        while (pas != 0)
        {
            if (st + pas <= n and aib1[st + pas] <= df)
            {
                sm_tot -= aib2[st + pas];
                df -= aib1[st + pas];
                st += pas;
            }
            pas /= 2;
        }
        if (df != 0)
        {
            st++;
            sm_tot -= rvalue[st] * df;
        }
        return sm_tot;
    }
};

int n, s, d, a[100005];
AIB ds;
int opt[100005], rsp[100005];

void divide(int l, int r, int st, int dr)
{
    if (l > r)
        return;
    int mij = (l + r) / 2;
    for (int i = r; i >= mij; i--)
        ds.update(a[i], 1);
    int bst = -1, unde;
    for (int i = st; i <= dr; i++)
    {
        ds.update(a[i], 1);
        int cr = ds.query(d - 2 * (s - mij) - (i - s));
        if (cr > bst)
        {
            bst = cr;
            unde = i;
        }
    }
    opt[mij] = unde;
    rsp[mij] = bst;
    for (int i = dr; i >= st; i--)
        ds.update(a[i], -1);
    divide(l, mij - 1, st, opt[mij]);
    for (int i = mij; i <= r; i++)
        ds.update(a[i], -1);
    divide(mij + 1, r, opt[mij], dr);
}

int solve()
{
    vector<int> all_values;
    for (int i = 1; i <= n; i++)
        all_values.push_back(a[i]);
    AIB ds_caz1;
    ds_caz1.init(all_values);
    int ans = 0;
    for (int i = s; i <= n; i++)
    {
        ds_caz1.update(a[i], 1);
        ans = max(ans, ds_caz1.query(d - (i - s)));
    }
    ds.init(all_values);
    for (int i = 1; i <= n; i++)
        opt[i] = 0;
    if (s == 1 or s == n)
        return ans;
    ds.update(a[s], 1);
    divide(1, s - 1, s + 1, n);
    for (int i = 1; i < s; i++)
        ans = max(ans, rsp[i]);
    /*for (int l = 1; l < s; l++)
    {
        int bst = -1, ps;
        for (int i = l; i < s; i++)
            ds.update(a[i], 1);
        for (int i = s; i <= n; i++)
        {
            ds.update(a[i], 1);
            int cr = ds.query(d - (i - s) - 2 * (s - l));
            if (cr > bst)
                bst = cr, ps = i;
        }
        for (int i = l; i <= n; i++)
            ds.update(a[i], -1);
        opt[l] = ps;
        if (l > 1 and opt[l] < opt[l - 1])
            assert(false);
        ans = max(ans, bst);
    }*/
    return ans;
}

long long findMaxAttraction(integer N, integer Start, integer D, integer Attraction[])
{
    n = N;
    s = Start + 1;
    d = D;
    for (int i = 1; i <= n; i++)
        a[i] = Attraction[i - 1];
    int ans = solve();
    s = n - s + 1;
    reverse(a + 1, a + n + 1);
    ans = max(ans, solve());
    return ans;
}

/*
5 2 7
10 2 20 30 1
*/

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