Submission #542149

#TimeUsernameProblemLanguageResultExecution timeMemory
542149Alex_tz307Colouring a rectangle (eJOI19_colouring)C++17
0 / 100
486 ms32148 KiB
#include <bits/stdc++.h> #define int long long using namespace std; const int kN = 2e5; const int64_t INF = 2e18L; int a[2 * kN], v[1 + kN + 1]; tuple<int, int, int> intervals[2 * kN]; vector<pair<int, int>> rEnd[1 + kN + 1]; void minSelf(int64_t &x, int64_t y) { if (y < x) { x = y; } } struct ST { int n; vector<int64_t> t, lazy; ST(int N) : n(N) { int dim = 1; while (dim < n + 1) { dim *= 2; } dim *= 2; t.resize(dim); lazy.resize(dim); } void push(int x) { if (lazy[x] == 0) { return; } for (int y = 2 * x; y <= 2 * x + 1; ++y) { t[y] += lazy[x]; lazy[y] += lazy[x]; } lazy[x] = 0; } void rangeAdd(int x, int lx, int rx, int st, int dr, int64_t v) { if (st <= lx && rx <= dr) { t[x] += v; lazy[x] += v; return; } push(x); int mid = (lx + rx) / 2; if (st <= mid) { rangeAdd(x * 2, lx, mid, st, dr, v); } if (mid < dr) { rangeAdd(x * 2 + 1, mid + 1, rx, st, dr, v); } t[x] = min(t[x * 2], t[x * 2 + 1]); } void rangeAdd(int st, int dr, int64_t v) { rangeAdd(1, 0, n, st, dr, v); } int64_t query(int x, int lx, int rx, int st, int dr) { if (st <= lx && rx <= dr) { return t[x]; } push(x); int mid = (lx + rx) / 2; int64_t ans = INF; if (st <= mid) { minSelf(ans, query(x * 2, lx, mid, st, dr)); } if (mid < dr) { minSelf(ans, query(x * 2 + 1, mid + 1, rx, st, dr)); } return ans; } int64_t query(int st, int dr) { return query(1, 0, n, st, dr); } }; int64_t solve(int n) { ST t(n); for (int i = 1; i <= n; ++i) { t.rangeAdd(i, i, t.query(0, i - 1)); t.rangeAdd(0, i - 1, v[i]); for (auto it : rEnd[i]) { int start, cost; tie(start, cost) = it; t.rangeAdd(start, i, cost); } } return t.query(n, n); } void testCase() { int n, m; cin >> n >> m; int N = n + m - 1; for (int i = 1; i <= N; ++i) { cin >> a[i]; } for (int i = 1; i <= N; ++i) { int cost; cin >> cost; int y = min(i - 1, m - 1); int x = i - 1 - y; int index = x - y + m; int len = min(i, N - i + 1); intervals[i] = {(index + 1) / 2, len, cost}; } int64_t ans = 0; for (int par = 0; par <= 1; ++par) { int M = (N + par) / 2 + 1; for (int i = 1; i <= M; ++i) { rEnd[i].clear(); } for (int i = 2 - par; i <= N; i += 2) { int index, len, cost; tie(index, len, cost) = intervals[i]; v[(i + par) / 2] = a[i]; rEnd[index + len - 1].emplace_back(index, cost); } v[M] = 0; ans += solve(M); } cout << ans << '\n'; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int tests = 1; for (int tc = 0; tc < tests; ++tc) { testCase(); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...