제출 #421380

#제출 시각아이디문제언어결과실행 시간메모리
421380timmyfeng모임들 (IOI18_meetings)C++17
0 / 100
91 ms7080 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[L][N], nxt_r[L][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 }; } } void calc(int k, int i) { if (nxt_r[k][i].par != -1 || k == 0) { return; } calc(k - 1, i); int p = nxt_r[k - 1][i].par; if (p != -1) { calc(k - 1, p); nxt_r[k][i] = combine(nxt_r[k - 1][i], nxt_r[k - 1][p]); } } 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 <= __lg(n); ++i) { for (int j = 0; j < n; ++j) { nxt_l[i][j].par = nxt_r[i][j].par = -1; } } vector<int> stk; for (int i = 0; i < n; ++i) { while (!stk.empty() && h[stk.back()] <= h[i]) { int j = stk.back(); stk.pop_back(); range mini = {0, 0, 0, i - 1}; for (int k = __lg(n); k >= 0; --k) { int p = nxt_l[k][mini.par].par; if (p >= j) { mini = combine(mini, nxt_l[k][mini.par]); } } nxt_r[0][j] = { mini.mini + h[j], (long long) h[j] * (i - j), i - j, i }; } if (!stk.empty()) { int j = stk.back(); range mini = {0, 0, 0, j + 1}; for (int k = __lg(n); k >= 0; --k) { calc(k, mini.par); int p = nxt_r[k][mini.par].par; if (p != -1 && p <= i) { mini = combine(mini, nxt_r[k][mini.par]); } } nxt_l[0][i] = { mini.mini + h[i], (long long) h[i] * (i - j), i - j, j }; for (int k = 1; k <= __lg(n); ++k) { int p = nxt_l[k - 1][i].par; if (p != -1) { nxt_l[k][i] = combine(nxt_l[k - 1][i], nxt_l[k - 1][p]); } } } stk.push_back(i); } vector<long long> c(q); for (int i = 0; i < q; ++i) { range left = {0, 0, 0, l[i]}; for (int k = __lg(n); k >= 0; --k) { calc(k, left.par); int p = nxt_r[k][left.par].par; if (p != -1 && p <= r[i]) { left = combine(left, nxt_r[k][left.par]); } } range right = {0, 0, 0, r[i]}; for (int k = __lg(n); k >= 0; --k) { int p = nxt_l[k][right.par].par; if (p >= l[i]) { right = combine(right, nxt_l[k][right.par]); } } int maxi = left.par; c[i] = min( left.mini + (long long) (r[i] - maxi + 1) * h[maxi], right.mini + (long long) (maxi - l[i] + 1) * h[maxi] ); } 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...