제출 #421919

#제출 시각아이디문제언어결과실행 시간메모리
421919Hegdahl모임들 (IOI18_meetings)C++17
0 / 100
1587 ms3276 KiB
#include <bits/stdc++.h> #include "meetings.h" using namespace std; using ll = long long; const ll INF = 1LL<<60; const int mxN = 75e4; const int offset = 2<<__lg(mxN-1); int n, q; vector<int> h; ll val[2*offset]; void upd(int i, ll x) { i += offset; val[i] += x; while (i /= 2) val[i] = min(val[2*i], val[2*i+1]); } ll qry(int i, int j) { i += offset-1; j += offset+1; ll ans = INF; while (i+1 < j) { if (i%2 == 0) ans = min(ans, val[i+1]); if (j%2 == 1) ans = min(ans, val[j-1]); i /= 2, j /= 2; } return ans; } void insert(int i) { for (int j = i, mx = h[i]; j < n; ++j) { mx = max(mx, h[j]); upd(j, mx); } for (int j = i-1, mx = h[i]; j >= 0; --j) { mx = max(mx, h[j]); upd(j, mx); } } void erase(int i) { for (int j = i, mx = 0; j < n; ++j) { mx = max(mx, h[j]); upd(j, -mx); } for (int j = i-1, mx = 0; j >= 0; --j) { mx = max(mx, h[j]); upd(j, -mx); } } ll solve(int L, int R) { static int CL = 0, CR = -1; while (CR < R) insert(++CR); while (CL > L) insert(--CL); while (CR > R) erase(CR--); while (CL < L) erase(CL++); return qry(L, R); } vector<ll> minimum_costs(vector<int> h_, vector<int> l, vector<int> r) { h = h_; n = (int)h.size(); q = (int)l.size(); vector<ll> ans(q); const int R = sqrt(n); vector<int> s(q); iota(s.begin(), s.end(), 0); sort(s.begin(), s.end(), [&](int i, int j) -> bool { if (l[i]/R != l[j]/R) return l[i]/R < l[j]/R; return (r[i]>r[j])^l[i]; }); for (int qq : s) ans[qq] = solve(l[qq], r[qq]); 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...