제출 #81155

#제출 시각아이디문제언어결과실행 시간메모리
81155polyfish전선 연결 (IOI17_wiring)C++14
13 / 100
267 ms24260 KiB
//pantyhose(black) + glasses = infinity #include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << " = " << x << '\n'; #define BP() cerr << "OK!\n"; #define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';} #define FILE_NAME "data" const int64_t INF = 1e18; const int64_t MAX_N = 200002; struct segment_tree { int64_t n; vector<int64_t> st; segment_tree(int64_t _n) { n = _n; st.resize(4*n, INF); } void upd(int64_t pos, int64_t val, int64_t l, int64_t r, int64_t id) { if (pos<l || pos>r) return; if (pos==l && r==pos) { st[id] = min(st[id], val); return; } int64_t mid = (l + r) / 2; upd(pos, val, l, mid, id*2); upd(pos, val, mid+1, r, id*2+1); st[id] = min(st[id*2], st[id*2+1]); } int64_t get(int64_t u, int64_t v, int64_t l, int64_t r, int64_t id) { if (v<l || u>r) return INF; if (u<=l && r<=v) return st[id]; int64_t mid = (l + r) / 2; return min(get(u, v, l, mid, id*2), get(u, v, mid+1, r, id*2+1)); } void upd(int64_t pos, int64_t val) { upd(pos, val, 1, n, 1); } int64_t get(int64_t u, int64_t v) { if (u>v) return INF; return get(u, v, 1, n, 1); } }; vector<pair<int64_t, int64_t> > all; int64_t n, _prev[MAX_N], _next[MAX_N]; int64_t ps[MAX_N], f[MAX_N]; void init(vector<int> r, vector<int> b) { for (auto v : r) all.push_back(make_pair(v, 1)); for (auto v : b) all.push_back(make_pair(v, 0)); sort(all.begin(), all.end()); n = all.size() - 1; for (int64_t i=1; i<=n; ++i) { ps[i] = ps[i-1] + all[i].first; } _prev[1] = 1; for (int64_t i=2; i<=n; ++i) { if (all[i].second==all[i-1].second) _prev[i] = _prev[i-1]; else _prev[i] = i; } _next[n] = n; for (int64_t i=n-1; i>=1; --i) { if (all[i].second==all[i+1].second) _next[i] = _next[i+1]; else _next[i] = i; } } int64_t min_total_length(vector<int> r, vector<int> b) { all.resize(1); init(r, b); for (int64_t i=1; i<=n; ++i) f[i] = INF; segment_tree tree1(n), tree2(n); tree1.upd(1, f[0] - all[_next[1]].first); tree2.upd(1, f[0] - all[_next[1]+1].first); for (int64_t i=_next[1]+1; i<=n; ++i) { int64_t l = max(_prev[_prev[i]-1], 2*_prev[i]-i-1); int64_t r = _prev[i]-1; f[i] = tree1.get(l, r) + ps[i] - 2*ps[_prev[i]-1] - (int64_t)(i - 2*_prev[i]+1)*all[_prev[i]-1].first; l = _prev[_prev[i]-1]; r = min(_prev[i]-1, 2*_prev[i]-i-1); f[i] = min(f[i], tree2.get(l, r) + ps[i] - 2*ps[_prev[i]-1] + (int64_t)(2*_prev[i]-i-1)*all[_prev[i]].first); if (_next[i]!=n) { tree1.upd(i+1, min(f[i], f[i+1]) + ps[i] - 1LL * (i+1) * all[_next[i+1]].first); tree2.upd(i+1, min(f[i], f[i+1]) + ps[i] - 1LL * (i+1) * all[_next[i+1]+1].first); } } return f[n]; } //int main() { // #ifdef GLASSES_GIRL // freopen(FILE_NAME".inp", "r", stdin); // //freopen(FILE_NAME".out", "w", stdout); // #endif // ios::sync_with_stdio(0); cin.tie(0); // int64_t m, n; // cin >> m >> n; // vector<int> r(m), b(n); // for (int64_t i=0; i<m; ++i) // cin >> r[i]; // for (int64_t i=0; i<n; ++i) // cin >> b[i]; // cout << min_total_length(r, b); //}
#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...