제출 #796554

#제출 시각아이디문제언어결과실행 시간메모리
796554thimote75Cake 3 (JOI19_cake3)C++14
0 / 100
1 ms384 KiB
#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 <= min(optb, mid); opti ++) { if (opti + M - 1 > mid) break ; int locv = queryTree.sumQuery( M, opti, mid ) + 2 * (perles[opti].p_ta - perles[mid].p_ta); 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, N, 0, N - 1) << endl; }

컴파일 시 표준 에러 (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 ++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...