Submission #572775

#	Time	Username	Problem	Language	Result	Execution time	Memory
572775		kartel	Carnival Tickets (IOI20_tickets)	C++14	27 / 100	1772 ms	76236 KiB

tickets

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
//#include "grader.cpp"
#include "tickets.h"
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

typedef tree<pair <int, int> , null_type, less<pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

long long find_maximum(int k, vector <vector <int> > x) {
    int n = sz(x);
    int m = sz(x[0]);

    vector <vector <int> > ans(n, vector <int> (m, -1));
    vector <int> le(n, 0);
    vector <int> ri(n, m - 1);
    ll sum = 0;
    for (int it = 0; it < k; it++) {
        vector <pair <int, pair <int, int> > > vl;
        ll curL = 0, curR = 0;
        ll mx = -1, mI = 0, mJ = 0;
        ordered_set se;
        for (int i = 0; i < n; i++) {
            while (le[i] < m && ans[i][le[i]] != -1) {
                le[i]++;
            }
            while (ri[i] >= 0 && ans[i][ri[i]] != -1) {
                ri[i]--;
            }
            vl.pb({x[i][le[i]], {x[i][ri[i]] + x[i][le[i]], i}});
            curR += x[i][ri[i]];
        }

        auto add = [&](int val, int i) {
            if (sz(se) < n / 2 - 1) {
                se.insert({val, i});
                curL += x[i][le[i]];
                return;
            }
            if (se.order_of_key(make_pair(val, 1e9)) < n / 2 - 1) {
                auto it = *se.find_by_order(n / 2 - 2);
                curR += x[it.S][ri[it.S]]; curL -= x[it.S][le[it.S]];
                curL += x[i][le[i]];
            } else {
                curR += x[i][ri[i]];
            }
            se.insert({val, i});
        };

        auto del = [&](int val, int i) {
            if (sz(se) <= n / 2 - 1) {
                se.erase({val, i});
                curL -= x[i][le[i]];
                return;
            }
            se.erase({val, i});
            if (se.order_of_key(make_pair(val, 1e9)) < n / 2 - 1) {
                auto it = *se.find_by_order(n / 2 - 2);
                curR -= x[it.S][ri[it.S]]; curL += x[it.S][le[it.S]];
                curL -= x[i][le[i]];
            } else {
                curR -= x[i][ri[i]];
            }
        };

        sort(all(vl));

        vector <pair <int, pair <int, int> > > a;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (ans[i][j] == -1) {
                    a.pb({x[i][j], {i, j}});
                }
            }
        }
        sort(all(a));

        int j = 0;
        for (int i = 0; i < sz(a); i++) {
            int val = a[i].F, I = a[i].S.F, J = a[i].S.S;

            while (j < sz(vl) && vl[j].F <= val) {
                curR -= x[vl[j].S.S][ri[vl[j].S.S]];
                add(vl[j].S.F, vl[j].S.S);
                j++;
            }
            del(x[I][ri[I]] + x[I][le[I]], I);
            if (sz(se) >= n / 2 - 1 && mx < val * 1ll * (n / 2 - 1) - curL + curR - val * 1ll * (n - n / 2)) {
                mx = val * 1ll * (n / 2 - 1) - curL + curR - val * 1ll * (n - n / 2);
                mI = I; mJ = J;
            }

            add(x[I][ri[I]] + x[I][le[I]], I);
        }
//        assert(mx != -1);
        set <pair <int, int> > sse;
        for (int i = 0; i < n; i++) {
            if (mI == i) {
                continue;
            }
            if (x[i][le[i]] <= x[mI][mJ]) {
                sse.insert({x[i][ri[i]] + x[i][le[i]], i});
            } else {
                sse.insert({2e9, i});
            }
        }

        int tmp = 0;
        for (auto [val, i] : sse) {
            if (tmp == n / 2 - 1) {
                ans[i][ri[i]] = it;
                continue;
            }
            tmp++;
            ans[i][le[i]] = it;
        }
        ans[mI][mJ] = it;
        sum += mx;
    }
    allocate_tickets(ans);
    return sum;
}

Compilation message (stderr)

tickets.cpp: In lambda function:
tickets.cpp:46:54: warning: comparison of integer expressions of different signedness: '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, std::less<std::pair<int, int> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |             if (se.order_of_key(make_pair(val, 1e9)) < n / 2 - 1) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
tickets.cpp: In lambda function:
tickets.cpp:63:54: warning: comparison of integer expressions of different signedness: '__gnu_pbds::tree_order_statistics_node_update<__gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_node_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, __gnu_pbds::detail::bin_search_tree_const_it_<__gnu_pbds::detail::rb_tree_node_<std::pair<int, int>, long unsigned int, std::allocator<char> >*, std::pair<int, int>, std::pair<int, int>*, const std::pair<int, int>*, std::pair<int, int>&, const std::pair<int, int>&, true, std::allocator<char> >, std::allocator<char> >, std::less<std::pair<int, int> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |             if (se.order_of_key(make_pair(val, 1e9)) < n / 2 - 1) {
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
tickets.cpp: In function 'long long int find_maximum(int, std::vector<std::vector<int> >)':
tickets.cpp:115:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  115 |         for (auto [val, i] : sse) {
      |                   ^

• Subtask 1: 11 / 11
• Subtask 2: 16 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10