제출 #41400

#제출 시각아이디문제언어결과실행 시간메모리
41400NurlykhanPalembang Bridges (APIO15_bridge)C++14
63 / 100
2039 ms3616 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define f first #define s second #define pb push_back #define mp make_pair #define ll long long #define ld long double #define sz(v) int(v.size()) #define all(v) v.begin(), v.end() #define vec vector<int> #define dead not_bad #define bad gooood #define left not_right #define y1 what using namespace std; const int N = (int) 2e5 + 10; const int M = (int) 2e6; const ll LINF = (ll) 2e18; const int INF = (int) 1e9 + 7; const int ALPHA = 26; const int mod = INF; const double PI = 3.14159265359; const ld EPS = (ld) 1e-12; const int nx[4] = {0, 0, -1, 1}; const int ny[4] = {1, -1, 0, 0}; vector<ll> a, b; int k, n; ll get1(ll x1, ll x2) { ll cur = 0; for (int i = 0; i < sz(a); i++) { ll val1, val2; if (a[i] <= x1 && x1 <= b[i]) { val1 = b[i] - a[i]; } else if (a[i] > x1) { val1 = a[i] + b[i] - 2 * x1; } else { val1 = 2 * x1 - (a[i] + b[i]); } if (a[i] <= x2 && x2 <= b[i]) { val2 = b[i] - a[i]; } else if (a[i] > x2) { val2 = a[i] + b[i] - 2 * x2; } else { val2 = 2 * x2 - (a[i] + b[i]); } cur += min(val1, val2); } return cur; } ll get(ll x) { ll cur = 0; for (int i = 0; i < sz(a); i++) { if (a[i] <= x && x <= b[i]) { cur += b[i] - a[i]; } else if (a[i] > x) { cur += a[i] + b[i] - 2 * x; } else if (b[i] < x) { cur += 2 * x - (a[i] + b[i]); } else { assert(0); } } if (k == 2) { ll l = 0, r = INF; while (r - l > 2) { ll m1 = l + (r - l) / 3; ll m2 = r - (r - l) / 3; if (get1(m1, x) > get1(m2, x)) { l = m1; } else { r = m2; } } for (ll i = l; i <= r; i++) cur = min(cur, get1(i, x)); } return cur; } ll solve() { ll l = 0, r = INF; while (r - l > 2) { ll m1 = l + (r - l) / 3; ll m2 = r - (r - l) / 3; if (get(m1) > get(m2)) { l = m1; } else { r = m2; } } ll ans = LINF; for (ll i = l; i <= r; i++) { ans = min(ans, get(i)); } return ans + sz(a); } int main() { #define fn "teams" #ifdef witch freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else //freopen(fn".in", "r", stdin); //freopen(fn".out", "w", stdout); #endif ll ans = 0; cin >> k >> n; for (int i = 1; i <= n; i++) { char ta, tb; ll x1, x2; cin >> ta >> x1 >> tb >> x2; //cout << ta << ' ' << x1 << ' ' << tb << ' ' << x2 << endl; if (x1 > x2) swap(x1, x2); if (ta == tb) { ans += x2 - x1; } else { a.pb(x1); b.pb(x2); } } cout << ans + solve(); 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...