Submission #389985

#TimeUsernameProblemLanguageResultExecution timeMemory
389985KeshiWiring (IOI17_wiring)C++17
13 / 100
206 ms18348 KiB
//In the name of God #include <bits/stdc++.h> #include "wiring.h" using namespace std; typedef long long ll; typedef pair<ll, ll> pll; const ll maxn = 2e5 + 100; const ll mod = 1e9 + 7; const ll inf = 1e18; #define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout); #define pb push_back #define Mp make_pair #define F first #define S second #define Sz(x) ll((x).size()) #define all(x) (x).begin(), (x).end() #define lc (id << 1) #define rc (lc | 1) pll seg[maxn << 2]; void upd(ll id, ll s, ll e, ll i, pll x){ if(i < s || e <= i) return; if(e - s == 1){ seg[id] = x; return; } ll mid = (s + e) >> 1; upd(lc, s, mid, i, x); upd(rc, mid, e, i, x); seg[id].F = min(seg[lc].F, seg[rc].F); seg[id].S = min(seg[lc].S, seg[rc].S); return; } pll get(ll id, ll s, ll e, ll l, ll r){ if(r <= s || e <= l) return Mp(inf, inf); if(l <= s && e <= r) return seg[id]; ll mid = (s + e) >> 1; pll p1 = get(lc, s, mid, l, r); pll p2 = get(rc, mid, e, l, r); return Mp(min(p1.F, p2.F), min(p1.S, p2.S)); } ll ls[maxn], dp[maxn]; vector<pll> a; long long min_total_length(vector<int> r, vector<int> b){ for(ll i : r){ a.pb(Mp(i, 0)); } for(ll j : b){ a.pb(Mp(j, 1)); } sort(all(a)); ll las[2] = {-1, -1}; ll n = Sz(a); ll ps = 0, ps2; for(ll i = 0; i < n; i++){ // cout << "# " << a[i].F << " " << a[i].S << " - " << dp[i] << "\n"; ls[i] = las[a[i].S ^ 1]; las[a[i].S] = i; ll j = ls[i]; dp[i + 1] = inf; if(j == -1) continue; if(i - j == 1){ ps = ps2 = 0; dp[i + 1] = dp[i] + a[i].F - a[i - 1].F; ll x = 0, x2 = 0; for(ll k = j; k > ls[j]; k--){ x += a[i - 1].F - a[k].F; x2 += a[i].F - a[k].F; // cout << "! " << k << " " << dp[k] + x << " " << dp[k] + x2 << "\n"; upd(1, 0, n, k, Mp(dp[k] + x, dp[k] + x2)); } } ps += a[i].F - a[j + 1].F; ps2 += a[i].F - a[j].F; pll p1 = get(1, 0, n, max(2 * j - i + 1, ls[j] + 1), j + 1); pll p2 = get(1, 0, n, ls[j] + 1, 2 * j - i + 1); /* cout << "? " << 2 * j - i << "\n"; cout << p1.F << " " << p1.S << " " << p2.F << " " << p2.S << "\n"; cout << ps << " " << ps2 << "\n";*/ dp[i + 1] = min(dp[i + 1], p1.F + ps2); dp[i + 1] = min(dp[i + 1], p2.S + ps); } return dp[n]; } /*int main(){ fast_io; return 0; }*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:82:7: warning: 'ps2' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |   ps2 += a[i].F - a[j].F;
      |       ^
#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...