제출 #421333

#제출 시각아이디문제언어결과실행 시간메모리
421333timmyfeng모임들 (IOI18_meetings)C++17
0 / 100
52 ms6228 KiB
#include <bits/stdc++.h> using namespace std; #include "meetings.h" const int N = 750000, L = __lg(N) + 1; long long mini_l[L][N], mini_r[L][N], sum_l[L][N], sum_r[L][N]; int par_l[L][N], par_r[L][N]; vector<int> h; void calc(int i, int l) { if (par_r[i][l] != -1 || i == 0) { return; } calc(i - 1, l); int p = par_r[i - 1][l]; if (p == -1) { return; } calc(i - 1, p); par_r[i][l] = par_r[i - 1][p]; sum_r[i][l] = sum_r[i - 1][l] + sum_r[i - 1][p]; mini_r[i][l] = min( (long long) h[p] * (p - l) + mini_r[i - 1][p], mini_r[i - 1][l] + sum_r[i - 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) { par_l[i][j] = par_r[i][j] = -1; sum_l[i][j] = sum_r[i][j] = 0; mini_l[i][j] = mini_r[i][j] = 0; } } vector<int> stk; for (int r = 0; r < n; ++r) { while (!stk.empty() && h[stk.back()] <= h[r]) { int l = stk.back(); stk.pop_back(); int u = r - 1; long long mini = 0; for (int i = __lg(n); i >= 0; --i) { if (par_l[i][u] >= l) { mini = min( (long long) h[u] * (r - 1 - u) + mini_l[i][u], mini + sum_l[i][u] ); u = par_l[i][u]; } } mini += h[l]; par_r[0][l] = r; mini_r[0][l] = mini; sum_r[0][l] = (long long) h[l] * (r - l); } if (!stk.empty()) { int l = stk.back(); int u = l + 1; long long mini = 0; for (int i = __lg(n); i >= 0; --i) { calc(i, u); if (par_r[i][u] != -1) { mini = min( (long long) h[u] * (u - l - 1) + mini_r[i][u], mini + sum_r[i][u] ); u = par_r[i][u]; } } mini += h[r]; par_l[0][r] = l; mini_l[0][r] = mini; sum_l[0][r] = (long long) h[r] * (r - l); for (int i = 1; i <= __lg(n); ++i) { int p = par_l[i - 1][r]; if (p != -1) { par_l[i][r] = par_l[i - 1][p]; sum_l[i][r] = sum_l[i - 1][r] + sum_l[i - 1][p]; mini_l[i][r] = min( (long long) h[p] * (r - p) + mini_l[i - 1][p], mini_l[i - 1][r] + sum_l[i - 1][p] ); } } } stk.push_back(r); } vector<long long> c(q); for (int i = 0; i < q; ++i) { int u = l[i]; long long left = 0; for (int j = __lg(n); j >= 0; --j) { calc(j, u); int p = par_r[j][u]; if (p != -1 && p <= r[i]) { left = min( (long long) h[u] * (u - l[i]) + mini_r[j][u], left + sum_r[j][u] ); u = p; } } left += (long long) (r[i] - u + 1) * h[u]; u = r[i]; long long right = 0; for (int j = __lg(n); j >= 0; --j) { int p = par_l[j][u]; if (p >= l[i]) { right = min( (long long) h[u] * (r[i] - u) + mini_l[j][u], right + sum_l[j][u] ); u = p; } } right += (long long) (u - l[i] + 1) * h[u]; c[i] = min(left, right); } 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...