Submission #711274

#	Time	Username	Problem	Language	Result	Execution time	Memory
711274		pls33	Swimming competition (LMIO18_plaukimo_varzybos)	C++17	100 / 100	1243 ms	178360 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#pragma region dalykai

template <typename F>
void _debug(F f)
{
    f();
}

#ifndef _AAAAAAAAA
#define debug(x)
#else
#define debug(x) _debug(x)
#endif

using p32 = pair<int, int>;
using p32u = pair<uint32_t, uint32_t>;
using p64 = pair<int64_t, int64_t>;
using p64u = pair<uint64_t, uint64_t>;
using vi16 = vector<int16_t>;
using vi16u = vector<uint16_t>;
using vi32 = vector<int>;
using vi32u = vector<uint32_t>;
using vi64 = vector<int64_t>;
using vi64u = vector<uint64_t>;
using vp32 = vector<p32>;
using vp32u = vector<p32u>;
using vp64 = vector<p64>;
using vp64u = vector<p64u>;
using vvi32 = vector<vi32>;
using vvi32u = vector<vi32u>;
using vvi64 = vector<vi64>;
using vvi64u = vector<vi64u>;
using vvp32 = vector<vp32>;
using vvp32u = vector<vp32u>;
using vvp64 = vector<vp64>;
using vvp64u = vector<vp64u>;

#pragma endregion

using change_t = vector<vector<pair<int, bool>>>;
void fix_multisets(int i,
                   change_t &insert, change_t &erase,
                   multiset<int> &opt, multiset<int> &diff)
{
    for (auto &[val, which] : insert[i])
    {
        if (which)
        {
            opt.insert(val);
        }
        else
        {
            diff.insert(val);
        }
    }
    for (auto &[val, which] : erase[i])
    {
        if (which)
        {
            auto it = opt.find(val);
            opt.erase(it);
        }
        else
        {
            auto it = diff.find(val);
            diff.erase(it);
        }
    }
}

int main()
{
#ifndef _AAAAAAAAA
    // freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.in", "r", stdin);
    // freopen("lmio_2018_3e2_plaukimo_varzybos_vyr.out", "w", stdout);
    //  ios_base::sync_with_stdio(false);
    //  cin.tie(0);
#else
    freopen("swim.in", "r", stdin);
#ifndef __linux__
    atexit([]()
           {
        freopen("con", "r", stdin);
        system("pause"); });
#endif
#endif

    int n, l, u;
    cin >> n >> l >> u;

    vi32 nums(n);
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }

    sort(nums.begin(), nums.end());

    vi32 dp(n, INT_MAX);
    vvp32 change(n + 1);

    // true jei is opt
    vector<vector<pair<int, bool>>> erase(n + 1), insert(n + 1);

    multiset<int> opt, diff;

    insert[min(n, l - 1)].emplace_back(nums[0], false);
    erase[min(n, u)].emplace_back(nums[0], false);
    fix_multisets(0, insert, erase, opt, diff);

    // kazkaip reikia pradzia (i = 0) sutvarkyt

    for (int i = 1; i < n; i++)
    {
        fix_multisets(i, insert, erase, opt, diff);
        if (opt.size())
        {
            dp[i] = min(dp[i], *opt.begin());
        }
        if (diff.size())
        {
            dp[i] = min(dp[i], nums[i] - *diff.rbegin());
        }

        if (i >= n - 1 || dp[i] == INT_MAX)
        {
            continue;
        }

        int bound = dp[i] + nums[i + 1];
        int lower = min(n, i + l);
        int upper = min(n, i + u);

        if (lower == n)
        {
            continue;
        }

        bound = (int)distance(nums.begin(), upper_bound(nums.begin(), nums.end(), bound));

        if (bound < lower)
        {
            insert[min(n, lower)].emplace_back(nums[i + 1], false);
            erase[min(n, upper + 1)].emplace_back(nums[i + 1], false);
            continue;
        }

        insert[lower].emplace_back(dp[i], true);
        if (bound > upper)
        {
            erase[min(n, upper + 1)].emplace_back(dp[i], true);
        }
        else
        {
            erase[bound].emplace_back(dp[i], true);
            insert[bound].emplace_back(nums[i + 1], false);
            erase[min(n, upper + 1)].emplace_back(nums[i + 1], false);
        }
    }

    debug([&]()
          {
              for (auto &a : dp)
              {
                  cout << a << ' ';
              }
              cout << '\n';
              //
          });

    cout << dp.back() << '\n';

    return 0;
}

Compilation message (stderr)

plaukimo_varzybos.cpp:8: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    8 | #pragma region dalykai
      | 
plaukimo_varzybos.cpp:45: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   45 | #pragma endregion
      |

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40