제출 #796548

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796548		thimote75	Cake 3 (JOI19_cake3)	C++14	컴파일 에러	0 ms	0 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;
    }
};
 
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 + M - 1 < 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]);
            }
 
            assert(sum == queryTree.sumQuery(M, left, right));
            
            int result = 2 * (perles[left].p_ta - perles[right].p_ta) + sum;
        
            max_result = max(max_result, result);
        }
    }
 
    cout << max_result << endl;
    queryTree->del();
}

컴파일 시 표준 에러 (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 ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
cake3.cpp: In function 'int main()':
cake3.cpp:188:14: error: base operand of '->' has non-pointer type 'WaveletTree'
  188 |     queryTree->del();
      |              ^~