제출 #588665

#제출 시각아이디문제언어결과실행 시간메모리
588665dnass전선 연결 (IOI17_wiring)C++17
13 / 100
324 ms16776 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; typedef long long int lld; #define INF 1000000000000000000LL lld xx, yy, n; vector<pair<lld, lld> > a; vector<lld> dp; struct item{ //ALTERAR lld val; item(){ val = INF; } item(lld valval){ val = valval; } }; item merge_neut = item(INF); //ALTERAR item apply_neut = item(0); //ALTERAR item merge(item a, item b){ //ALTERAR return a.val<b.val?a:b; } item apply_lazy(item x, item l, lld len){ //ALTERAR return item(x.val+l.val); } item apply_lazy_pure(item x, item l){ //ALTERAR return item(x.val+l.val); } item build_leaf(lld pos){ //ALTERAR return item(0); } struct ST{ vector<item> st; vector<item> lazy; void init(){ lld sz = 1; while(sz<n) sz*=2; st.resize(2*sz); lazy.resize(2*sz); } void build(lld v = 1, lld tl = 0, lld tr = n-1){ if(tl==tr) { st[v] = build_leaf(tl); lazy[v] = apply_neut; }else{ lld tm = (tl+tr)/2; build(2*v, tl, tm); build(2*v+1,tm+1,tr); st[v] = merge(st[2*v], st[2*v+1]); lazy[v] = apply_neut; } } void push(int v, int tl, int tr){ st[v] = apply_lazy(st[v], lazy[v], tr-tl+1); if(tl!=tr){ lazy[2*v] = apply_lazy_pure(lazy[2*v], lazy[v]); lazy[2*v+1] = apply_lazy_pure(lazy[2*v+1], lazy[v]); } lazy[v] = apply_neut; } item query(lld l, lld r, lld v = 1, lld tl=0, lld tr=n-1){ push(v, tl, tr); if(l>r) return merge_neut; if(l<=tl&&tr<=r){ return st[v]; } lld tm = (tl+tr)/2; return merge(query(l,min(r,tm),2*v, tl, tm),query(max(l, tm+1), r, 2*v+1, tm+1,tr)); } void upd(lld l, lld r, item val, lld v=1,lld tl=0, lld tr=n-1){ push(v,tl,tr); if(l>r) return; if(l<=tl&&tr<=r){ lazy[v] = apply_lazy_pure(lazy[v], val); push(v,tl,tr); return; } lld tm = (tl+tr)/2; upd(l,min(r,tm), val, 2*v, tl, tm); upd(max(l,tm+1),r, val, 2*v+1, tm+1, tr); st[v] = merge(st[2*v], st[2*v+1]); } }; ST seg; lld min_total_length(vector<int> r, vector<int> b){ xx = (lld) r.size(); yy = (lld) b.size(); n = xx+yy; for(lld i=0;i<xx;i++) a.push_back({r[i], 1}); for(lld i=0;i<yy;i++) a.push_back({b[i], -1}); sort(a.begin(), a.end()); a.push_back({INF, 0}); dp.resize(n+1); dp[n]=0; lld block = 0; lld nxt_beg = n, nxt_end = n, this_end = n; seg.init(); seg.build(); for(lld i=n-1;i>=0;i--){ if(a[i].second!=a[i+1].second){ block++; nxt_beg = i+1; nxt_end = this_end; this_end = i; if(block==1){ dp[i] = INF; continue; } lld sum_ai = 0; for(lld j=nxt_beg;j<=nxt_end;j++){ sum_ai += a[j].first; seg.upd(j, j, sum_ai-(j+1-nxt_beg)*a[i].first+dp[j+1]); } }else{ if(block==1){ dp[i] = INF; continue; } lld pos_block = nxt_beg-i-1; seg.upd(nxt_beg, nxt_beg+pos_block-1, a[nxt_beg].first-a[i].first); seg.upd(nxt_beg+pos_block, nxt_end, a[nxt_beg-1].first-a[i].first); } dp[i] = seg.query(nxt_beg, nxt_end).val; } return dp[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...