제출 #971799

#제출 시각아이디문제언어결과실행 시간메모리
971799fve5모임들 (IOI18_meetings)C++17
19 / 100
559 ms2340 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; struct Info { int len, pref, suff, sub; Info(int len, int pref, int suff, int sub) : len(len), pref(pref), suff(suff), sub(sub) { } Info(int val) : Info(1, !val, !val, !val) { } Info() : Info(1, 0, 0, 0) { } }; Info merge(const Info &a, const Info &b) { return {a.len + b.len, a.pref + (a.pref == a.len) * b.pref , b.suff + (b.suff == b.len) * a.suff, max({a.sub, b.sub, a.suff + b.pref})}; } struct SegTree { vector<Info> arr; int s; Info query(int l, int r) { Info ans_l, ans_r; for (l += s, r += s; l < r; l >>= 1, r >>= 1) { if (l & 1) ans_l = merge(ans_l, arr[l++]); if (r & 1) ans_r = merge(arr[--r], ans_r); } return merge(ans_l, ans_r); } SegTree(int N, const vector<int> &a) { s = 1 << (int)ceil(log2(N)); arr.resize(2 * s); for (int i = 0; i < N; i++) arr[i + s] = Info(a[i]); for (int i = s - 1; i; i--) arr[i] = merge(arr[2 * i], arr[2 * i + 1]); } }; vector<long long> minimum_costs(vector<int> H, vector<int> L, vector<int> R) { int N = H.size(); int Q = L.size(); vector<long long> ans(Q); if (Q <= 5000 && N <= 5000) { for (int i = 0; i < Q; i++) { vector<long long> cost_l(R[i] - L[i] + 2), cost_r(R[i] - L[i] + 2); stack<pair<int, int>> st; st.emplace(2e9, R[i] - L[i] + 1); for (int j = R[i] - L[i]; j >= 0; j--) { while (st.top().first <= H[j + L[i]]) st.pop(); cost_r[j] = cost_r[st.top().second] + (long long)H[j + L[i]] * (st.top().second - j); st.emplace(H[j + L[i]], j); } while (!st.empty()) st.pop(); st.emplace(2e9, 0); for (int j = 0; j <= R[i] - L[i]; j++) { while (st.top().first <= H[j + L[i]]) st.pop(); cost_l[j + 1] = cost_l[st.top().second] + (long long)H[j + L[i]] * (j + 1 - st.top().second); st.emplace(H[j + L[i]], j + 1); } ans[i] = 1e18; for (int j = 0; j <= R[i] - L[i]; j++) { ans[i] = min(ans[i], cost_l[j + 1] + cost_r[j] - H[j + L[i]]); } } } else { SegTree segtree(N, H); for (int i = 0; i < Q; i++) { ans[i] = R[i] - L[i] + 1 - segtree.query(L[i], R[i] + 1).sub; } } return ans; }
#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...