Submission #1087684

#TimeUsernameProblemLanguageResultExecution timeMemory
1087684SeungniTreatment Project (JOI20_treatment)C++17
4 / 100
89 ms13004 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pii = pair<ll, ll>; const ll inf = 0x3f3f3f3f3f3f3f3fLL; ll N, M, sz; pair<ll, pair<pii, ll>> arr[100005]; ll seg[200505 * 2]; void update(int pos, ll v) { pos += sz; seg[pos] = min(seg[pos], v); for (; pos > 0; pos >>= 1) seg[pos >> 1] = min(seg[pos], seg[pos ^ 1]); return; } ll query(int l, int r) { r++; ll ret = inf; for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) { if (l & 1) ret = min(ret, seg[l++]); if (r & 1) ret = min(ret, seg[--r]); } return ret; } void subtask_1() { vector<ll> v; v.push_back(0); v.push_back(1), v.push_back(N); for (int i = 0; i < M; i++) { v.push_back(arr[i].second.first.first); v.push_back(arr[i].second.first.second); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); sz = v.size(); sort(arr, arr + M, [&](pair<ll, pair<pii, ll>> a, pair<ll, pair<pii, ll>> b) { return a.second.first.second < b.second.first.second; }); for (int i = 0; i < M; i++) { ll L = arr[i].second.first.first, R = arr[i].second.first.second; L = lower_bound(v.begin(), v.end(), L) - v.begin(); R = lower_bound(v.begin(), v.end(), R) - v.begin(); arr[i].second.first = {L, R}; } vector<ll> dp(sz + 5, inf); memset(seg, 0x3f, sizeof(seg)); dp[0] = 0; update(0, dp[0]); for (int i = 0; i < M; i++) { ll l = arr[i].second.first.first, r = arr[i].second.first.second, c = arr[i].second.second; ll idx = lower_bound(v.begin(), v.end(), v[l] - 1) - v.begin(); dp[r] = min(dp[r], query(idx, r) + c); update(r, dp[r]); } int idx = lower_bound(v.begin(), v.end(), N) - v.begin(); if (dp[idx] == inf) cout << -1; else cout << dp[idx]; return; } void subtask_2() { ll ans = inf; sort(arr, arr + M); for (int i = 0; i < (1 << M); i++) { vector<int> v; ll cost = 0; for (int j = 0; j < M; j++) { if (i & (1 << j)) v.push_back(j), cost += arr[j].second.second; } vector<pair<pii, ll>> now; now.push_back({{1, N}, 0}); for (int j: v) { vector<pair<pii, ll>> nxt; ll T = arr[j].first, L = arr[j].second.first.first, R = arr[j].second.first.second; for (auto [range, t]: now) { ll l = range.first, r = range.second; l -= T - t, l = max(l, 1LL); r += T - t, r = min(r, N); if (l < L) nxt.push_back({{l, L - 1}, T}); if (r > R) nxt.push_back({{R + 1, r}, T}); } swap(nxt, now); } if (now.empty()) ans = min(ans, cost); } if (ans == inf) cout << -1; else cout << ans; return; } void solve() { cin >> N >> M; int sub_task1 = 1, sub_task2 = (M <= 16); for (int i = 0; i < M; i++) { ll T, L, R, C; cin >> T >> L >> R >> C; if (T != 1) sub_task1 = 0; arr[i] = {T, {{L, R}, C}}; } if (sub_task1) { subtask_1(); return; } if (sub_task2) { subtask_2(); return; } return; } int main(void) { ios::sync_with_stdio(false); cin.tie(0); int t = 1; //cin >> t; while (t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...