제출 #421995

#제출 시각아이디문제언어결과실행 시간메모리
421995timmyfeng모임들 (IOI18_meetings)C++17
0 / 100
21 ms2208 KiB
#include <bits/stdc++.h> using namespace std; #include "meetings.h" const int N = 750000, L = __lg(N) + 1; struct range { long long mini, sum; int size, par; } nxt_l[N], nxt_r[N]; vector<int> h; range combine(range l, range r) { if (r.par == -1) { return {0, 0, 0, -1}; } else { return { min(l.mini + r.sum, (long long) h[l.par] * l.size + r.mini), l.sum + r.sum, l.size + r.size, r.par }; } } vector<long long> minimum_costs(vector<int> h, vector<int> l, vector<int> r) { int n = h.size(), q = l.size(); ::h = h; for (int i = 0; i < n; ++i) { nxt_l[i].par = nxt_r[i].par = -1; } vector<int> less, greater; for (int i = 0; i < n; ++i) { while (!less.empty() && h[less.back()] < h[i]) { int j = less.back(); less.pop_back(); range mini = {0, 0, 0, i - 1}; while (true) { range temp = combine(mini, nxt_l[mini.par]); if (temp.par < j) { break; } mini = temp; } nxt_r[j] = { mini.mini + h[j], (long long) h[j] * (i - j), i - j, i }; } while (!greater.empty() && h[greater.back()] <= h[i]) { greater.pop_back(); } if (!greater.empty()) { int j = greater.back(); range mini = {0, 0, 0, j + 1}; while (true) { range temp = combine(mini, nxt_r[mini.par]); if (temp.par == -1 || temp.par > i) { break; } mini = temp; } nxt_l[i] = { mini.mini + h[i], (long long) h[i] * (i - j), i - j, j }; } greater.push_back(i); less.push_back(i); } vector<long long> c(q); for (int i = 0; i < q; ++i) { range left = {0, 0, 0, l[i]}; while (true) { range temp = combine(left, nxt_r[left.par]); if (temp.par == -1 || temp.par > r[i]) { break; } left = temp; } range right = {0, 0, 0, r[i]}; while (true) { range temp = combine(right, nxt_l[right.par]); if (temp.par < l[i]) { break; } right = temp; } c[i] = min( left.mini + (long long) (r[i] - left.par + 1) * h[left.par], right.mini + (long long) (right.par - l[i] + 1) * h[right.par] ); } return c; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...