제출 #792192

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
792192		thimote75	Cake 3 (JOI19_cake3)	C++14	24 / 100	4072 ms	213580 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;
    WaveletTree* right_tree;
    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 (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);
    }
};

signed main () {
    int N, M;
    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);

    int max_result = -1e18;
    for (int left = 0; left < N; left ++) {
        priority_queue<int> vs; int sum = 0;
        for (int i = left; i <= left + M - 1; i ++) {
            sum += beauty[i];
            vs.push(- beauty[i]);
        }
        for (int right = left + M - 1; right < N; right ++) {
            int low = - vs.top();
            if (low < beauty[right] && right != left + M - 1) {
                vs.pop();
                sum -= low;
                sum += beauty[right];
                vs.push(-beauty[right]);
            }
            
            int result = 2 * (perles[left].p_ta - perles[right].p_ta) + sum;
        
            max_result = max(max_result, result);
        }
    }

    cout << max_result << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In constructor 'WaveletTree::WaveletTree(idata, idata)':
cake3.cpp:46: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]
   46 |         for (int i = 0; i < local_values.size(); i ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~

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