Submission #542200

#TimeUsernameProblemLanguageResultExecution timeMemory
542200Alex_tz307Colouring a rectangle (eJOI19_colouring)C++17
100 / 100
482 ms30120 KiB
#include <bits/stdc++.h> using namespace std; const int kN = 2e5; const int64_t INF = 2e18L; int a[2 * kN], v[1 + kN]; tuple<int, int, int> intervals[2 * kN]; vector<pair<int, int>> rEnd[1 + kN]; 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.t[1]; } void testCase() { int n, m; cin >> n >> m; int N = n + m - 1; for (int i = 1; i <= N; ++i) { cin >> a[i]; } int cost; for (int i = 1; i <= N; ++i) { cin >> cost; int y = min(i - 1, m - 1); int x = i - 1 - y; int index = x - y + m; int len = min(y + 1, n - x); intervals[i] = {index, len, cost}; } int64_t ans = 0; for (int par = 0; par <= 1; ++par) { if (par == 0 && n == 1 && m == 1) { continue; } int p = get<0>(intervals[2 - par]) % 2; int M = (N + p) / 2; for (int i = 2 - p; i <= N; i += 2) { v[(i + p) / 2] = a[i]; } 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]; rEnd[(index + 1) / 2 + len - 1].emplace_back((index + 1) / 2, cost); } ans += solve(M); } cout << ans << '\n'; } int 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...