Submission #796568

#	Time	Username	Problem	Language	Result	Execution time	Memory
796568		thimote75	Cake 3 (JOI19_cake3)	C++14	100 / 100	930 ms	230392 KiB

cake3

#include <bits/stdc++.h>
#define int long long
#define p_be second
#define p_ta first

using namespace std;

using idata = vector<int>;
using t_perle = pair<int, int>;
using t_perles = vector<t_perle>;

struct WaveletTree {
    WaveletTree*  left_tree = nullptr;
    WaveletTree* right_tree = nullptr;
    int size;
 
    idata values;
    idata cumul;
 
    idata target_pos_left;
    idata target_pos_right;
 
    WaveletTree (idata local_values, idata sorted_values) {
        size = local_values.size();
        values = local_values;
 
        cumul.resize(local_values.size() + 1);
        for (int i = 0; i < size; i ++)
            cumul[i + 1] = cumul[i] + local_values[i];
 
        int pivot;
        if (sorted_values.size() == 1)
            pivot = sorted_values[0];
        else
            pivot = sorted_values[(sorted_values.size() - 1) >> 1];
 
        target_pos_left .resize(size, 0);
        target_pos_right.resize(size, 0);
 
        idata left_values;
        idata left_values_sorted;
        idata right_values;
        idata right_values_sorted;
 
        for (int i = 0; i < local_values.size(); i ++) {
            int u = local_values[i];
 
            if (u <= pivot) { 
                left_values.push_back(u);
                target_pos_left[i] ++;
            } else {
                right_values.push_back(u);
                target_pos_right[i] ++;
            }
        }
 
        for (int i = 1; i < size; i ++) {
            target_pos_right[i] += target_pos_right[i - 1];
            target_pos_left [i] += target_pos_left [i - 1];
        }
 
        for (int u : sorted_values) {
            if (u <= pivot) left_values_sorted.push_back(u);
            else right_values_sorted.push_back(u);
        }
 
        if (right_values.size() == 0) return ;
 
        left_tree  = new WaveletTree(left_values,  left_values_sorted);
        right_tree = new WaveletTree(right_values, right_values_sorted);
    }
    int sumQuery (int M, int left, int right) {
        return _sumQuery(M, left, right).second;
    }
    pair<int, int> _sumQuery (int M, int left, int right) {
        if (M < 0) {
            cout << "ERROR\n";
            exit(0);
        }
        if (left < 0 || right >= size) {
            cout << "ERROR\n";
            exit(0);
        }
        if (M == 0) return { 0, 0 };
        if (right - left + 1 <= M)
            return { right - left + 1, cumul[right + 1] - cumul[left] };
        if (right_tree == nullptr)
            return { M, cumul[M] };
        
        pair<int, int> right_result
         = right_tree->_sumQuery(
            M, 
            left == 0 ? 0 : target_pos_right[left - 1], 
            target_pos_right[right] - 1
        );
 
        if (M == right_result.first) return right_result;
 
        pair<int, int> left_result
         = left_tree->_sumQuery(
            M - right_result.first,
            left == 0 ? 0 : target_pos_left[left - 1],
            target_pos_left[right] - 1
        );
 
        return {
            left_result.first + right_result.first,
            left_result.second + right_result.second
        };
    }
 
    void show (int depth, int left, int right) {
        if (depth <= 0 || left_tree == nullptr) {
            cout << "[";
            for (int i = 0; i < size; i ++) {
                if (left <= i && i <= right)
                    cout << values[i] << ":" << cumul[i + 1] << ":" << target_pos_left[i] << ":" << target_pos_right[i];
                else cout << "-:-:-:-";
                if (i + 1 != size)
                    cout << ", ";
            }
            cout << "]";
            return ;
        }
 
        left_tree ->show(depth - 1, left == 0 ? 0 : target_pos_left [left - 1], target_pos_left [right] - 1);
        right_tree->show(depth - 1, left == 0 ? 0 : target_pos_right[left - 1], target_pos_right[right] - 1);
    }
    void del () {
        if (left_tree) left_tree->del();
        if (right_tree) right_tree->del();

        delete left_tree;
        delete right_tree;
    }
};

int N, M;
int solve (WaveletTree &queryTree, t_perles &perles, 
        int left, int right, int opta, int optb) {
    if (left == right) return -1e18;
    int mid = (left + right) >> 1;

    int optm = -1;
    int optv = -1e18;

    for (int opti = opta; opti <= optb; opti ++) {
        if (opti + M - 1 > mid) break ;

        int locv = queryTree.sumQuery( M - 2, opti + 1, mid - 1 ) + 2 * (perles[opti].p_ta - perles[mid].p_ta)
                 + perles[opti].p_be + perles[mid].p_be;
        if (locv <= optv) continue ;

        optm = opti;
        optv = locv;
    }

    if (left + 1 == right)
        return optv;
    
    int l_optv = solve(queryTree, perles, left, mid, opta, optm);
    int r_optv = solve(queryTree, perles, mid + 1, right, optm, optb);

    int o_optv = max(l_optv, r_optv);
    return max(optv, o_optv);
}

signed main () {
    cin >> N >> M;

    t_perles perles;
    set<int> beauty_set;
    for (int i = 0; i < N; i ++) {
        int b, t;
        cin >> b >> t;

        beauty_set.insert(b);
        perles.push_back({ t, b });
    }

    idata beauty_unique;
    for (int u : beauty_set) beauty_unique.push_back(u);

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

    idata beauty;
    for (const auto &perle : perles)
        beauty.push_back(perle.p_be);
    
    WaveletTree queryTree (beauty, beauty_unique);

    cout << solve(queryTree, perles, M - 1, N, 0, N - 1) << endl;
    queryTree.del();
}

Compilation message (stderr)

cake3.cpp: In constructor 'WaveletTree::WaveletTree(idata, idata)':
cake3.cpp:45:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int i = 0; i < local_values.size(); i ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76