제출 #521616

#제출 시각아이디문제언어결과실행 시간메모리
521616tkwiatkowski전선 연결 (IOI17_wiring)C++17
13 / 100
129 ms8584 KiB
/* Zadanie: Wiring Autor: Tomasz Kwiatkowski */ #include <bits/stdc++.h> #include "wiring.h" #define fi first #define se second #define pb push_back using namespace std; typedef long long ll; const int BASE = 1<<17; long long segTree[2*BASE + 7]; long long lazy[2*BASE + 7]; void Update(int v) { segTree[2*v] += lazy[v]; segTree[2*v + 1] += lazy[v]; lazy[2*v] += lazy[v]; lazy[2*v + 1] += lazy[v]; lazy[v] = 0; } void Add(int a, int b, long long val, int v = 1, int l = 0, int r = BASE - 1) { if (b < l || r < a) return; if (a <= l && r <= b) { segTree[v] += val; lazy[v] += val; return; } Update(v); int mid = (l + r) / 2; Add(a, b, val, 2*v, l, mid); Add(a, b, val, 2*v + 1, mid + 1, r); segTree[v] = min(segTree[2*v], segTree[2*v + 1]); } void Clear(int a, int b, int v = 1, int l = 0, int r = BASE - 1) { segTree[v] = 1e18; lazy[v] = 0; if (l == r) return; int mid = (l + r) / 2; if (l <= b) Clear(a, b, 2*v, l, mid); if (mid + 1 <= b) Clear(a, b, 2*v + 1, mid + 1, r); } long long min_total_length(vector<int> r, vector<int> b) { for (int i = 0; i < 2*BASE; ++i) segTree[i] = 1e18, lazy[i] = 0; int n = r.size(); int m = b.size(); int i, j; i = j = 0; vector<int> x; vector<bool> col; while (i < n && j < m) col.pb(r[i] < b[j]), x.pb((r[i] < b[j] ? r[i++] : b[j++])); while (i < n) col.pb(1), x.pb(r[i++]); while (j < m) col.pb(0), x.pb(b[j++]); segTree[1] = 0; long long ans = 0; int prv_k = 0; x.pb(x.back()); col.pb(!col.back()); for (int i = 0; i < n+m;) { //printf("starting: i = %d\n", i); int d = (i ? x[i] - x[i - 1] : 0); int j = i; int k = 0; vector<long long> dp; dp.pb(segTree[1]); //printf(" dp: %lld\n", dp.back()); long long sum = 0; long long tmp = 0; while (j < n+m && col[j] == col[i]) { ++k; Add(k, BASE - 1, -d); dp.pb(tmp + segTree[1]); //printf(" dp: %lld + %lld\n", tmp, segTree[1]); if (col[j + 1] == col[i]) { sum += x[j + 1] - x[j]; //printf(" sum = %lld\n", sum); tmp += sum; } ++j; } Clear(0, prv_k + 2); tmp = 0; sum = 0; ans = dp[dp.size()-1] + tmp + (ll)(dp.size()-1)*d; for (size_t a = 0; a < dp.size(); ++a) { Add(a, a, -(ll)1e18 + dp[dp.size()-1 - a] + tmp + (ll)a*(x[j] - x[j - 1]) + (ll)(dp.size()-1 - a)*d); //printf(" Add %lu: %lld + %lld + %lld + %lld\n", a, dp[dp.size()-1 - a], (ll)a*(x[j] - x[j - 1]), tmp, (ll)(dp.size()-1 - a)*d); if (a > 0) { sum += x[j - a] - x[j - a - 1]; tmp += sum; } } prv_k = dp.size(); i = j; } return ans; } // int main() // { // ios_base::sync_with_stdio(0), cin.tie(0); // 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...