Submission #435408

#TimeUsernameProblemLanguageResultExecution timeMemory
435408sinamhdvPalembang Bridges (APIO15_bridge)C++11
63 / 100
2080 ms28032 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int mod = 1000 * 1000 * 1000 + 7; const int INF = 1e9 + 100; const ll LINF = 1e18 + 100; #ifdef DEBUG #define dbg(x) cout << #x << " = " << (x) << endl << flush; #define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; } #else #define dbg(x) ; #define dbgr(s, f) ; #endif #define FOR(i, a, b) for (int i = (a); i < (int)(b); i++) #define fast_io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define all(x) (x).begin(), (x).end() #define pb push_back #define mp make_pair #define fr first #define sc second #define endl '\n' #define MAXN 100100 int k, n; int z1[MAXN], z2[MAXN], lft[MAXN], rgt[MAXN]; ll ans, sig; vector<int> cor; vector<int> beg[2 * MAXN], fin[2 * MAXN]; vector<int> goback[2 * MAXN]; int32_t main(void) { fast_io; cin >> k >> n; FOR(i, 0, n) { char c; cin >> c; z1[i] = c - 'A'; cin >> lft[i] >> c; z2[i] = c - 'A'; cin >> rgt[i]; if (lft[i] > rgt[i]) swap(lft[i], rgt[i]); ans += rgt[i] - lft[i] + (z1[i] != z2[i]); cor.pb(lft[i]); cor.pb(rgt[i]); sig += lft[i]; } dbgr(z1, z1 + n); dbgr(z2, z2 + n); ll bksum = 0, bkcnt = 0; ll fwsum = 0, fwcnt = 0; sort(all(cor)); cor.resize(unique(all(cor)) - cor.begin()); FOR(i, 0, n) { lft[i] = lower_bound(all(cor), lft[i]) - cor.begin(); rgt[i] = lower_bound(all(cor), rgt[i]) - cor.begin(); if (z1[i] == z2[i]) continue; beg[lft[i]].pb(i); fin[rgt[i]].pb(i); fwsum += cor[lft[i]]; fwcnt++; } FOR(i, 0, (int)cor.size()) { for (int u : beg[i]) { fwcnt--; fwsum -= cor[lft[u]]; dbg(u); } /* if (i == 4) { dbg(bkcnt); dbg(fwcnt); dbg(bksum); dbg(fwsum); dbg(cor[i]); }*/ sig = min(sig, cor[i] * bkcnt - bksum + fwsum - cor[i] * fwcnt); if (k == 2) { ll res = LINF; ll _fwsum = fwsum, _fwcnt = fwcnt; ll midsum = 0, midcnt = 0; ll midbksum = 0; FOR(j, i + 1, (int)cor.size()) { for (int u : beg[j]) { fwcnt--; fwsum -= cor[lft[u]]; } for (int u : goback[j]) { midbksum += cor[lft[u]] - cor[i]; midcnt--; midsum -= cor[rgt[u]]; } res = min(res, midbksum + cor[j] * midcnt - midsum + fwsum - cor[j] * fwcnt); for (int u : fin[j]) if (lft[u] > i) { midcnt++; midsum += cor[rgt[u]]; // assign go back int pos = lower_bound(all(cor), cor[rgt[u]] + cor[lft[u]] - cor[i]) - cor.begin(); if (pos < (int)cor.size()) goback[pos].pb(u); } } FOR(j, 0, 2 * MAXN) goback[j].clear(); fwsum = _fwsum; fwcnt = _fwcnt; res += cor[i] * bkcnt - bksum; sig = min(sig, res); } for (int u : fin[i]) { bkcnt++; bksum += cor[rgt[u]]; } } ans += 2 * sig; cout << ans << endl; 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...