Submission #743678

#	Time	Username	Problem	Language	Result	Execution time	Memory
743678		pls33	Swimming competition (LMIO18_plaukimo_varzybos)	C++17	100 / 100	1028 ms	178416 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