제출 #46608

#제출 시각아이디문제언어결과실행 시간메모리
46608tieunhiPalembang Bridges (APIO15_bridge)C++11
0 / 100
17 ms928 KiB
#include <bits/stdc++.h> #define pii pair<int, int> #define mp make_pair #define F first #define S second #define PB push_back #define N 100005 #define maxc 1000000007 using namespace std; int k, n, rr[2*N]; pii a[N]; long long f[2][N]; struct IntervalTree { long long t[N << 4]; int sz[N << 4]; void build(int l, int r, int id) { t[id] = sz[id] = 0; if (l == r) return; int mid = (r + l)/2; build(l, mid, id*2); build(mid+1, r, id*2+1); } void update(int l, int r, int id, int x, int val) { if (l == r) { t[id] += val; sz[id]++; return; } int mid = (r + l)/2; if (x <= mid) update(l, mid, id*2, x, val); else update(mid+1, r, id*2+1, x, val); t[id] += val; sz[id]++; } int getpos(int l, int r, int id, int x) { if (l == r) return l; int mid = (r + l)/2; if (sz[id*2] >= x) return getpos(l, mid, id*2, x); return getpos(mid+1, r, id*2+1, x-sz[id*2]); } long long get(int l, int r, int id, int x, int y) { if (l > y || r < x) return 0; if (l >= x && r <= y) return t[id]; int mid = (r + l)/2; long long a = get(l, mid, id*2, x, y); long long b = get(mid+1, r, id*2+1, x, y); return a + b; } int getSz(int l, int r, int id, int x, int y) { if (l > y || r < x) return 0; if (l >= x && r <= y) return sz[id]; int mid = (r + l)/2; int a = getSz(l, mid, id*2, x, y); int b = getSz(mid+1, r, id*2+1, x, y); return a + b; } }t; bool cmp(pii x, pii y) { return x.F + x.S < y.F + y.S; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("INP.TXT", "r", stdin); cin >> k >> n; int cur = 0; long long ans = 0; for (int i = 1; i <= n; i++) { char x, y; int u, v; cin >> x >> u >> y >> v; if (x == y) ans += abs(u-v); else { if (u > v) swap(u, v); a[++cur] = mp(u, v); } } n = cur; sort(a+1, a+n+1, cmp); cur = 0; for (int i = 1; i <= n; i++) { rr[++cur] = a[i].F; rr[++cur] = a[i].S; } sort(rr+1, rr+cur+1); cur = unique(rr+1, rr+cur+1) - rr - 1; for (int i = 1; i <= n; i++) { a[i].F = lower_bound(rr+1, rr+cur+1, a[i].F) - rr; a[i].S = lower_bound(rr+1, rr+cur+1, a[i].S) - rr; } for (int i = 1; i <= n; i++) { t.update(1, 2*n, 1, a[i].F, rr[a[i].F]); t.update(1, 2*n, 1, a[i].S, rr[a[i].S]); int pos = t.getpos(1, 2*n, 1, i); long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n); long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1); f[0][i] = xx + yy; } t.build(1, 2*n, 1); for (int i = n; i >= 1; i--) { t.update(1, 2*n, 1, a[i].F, rr[a[i].F]); t.update(1, 2*n, 1, a[i].S, rr[a[i].S]); int pos = t.getpos(1, 2*n, 1, i); long long xx = t.get(1, 2*n, 1, pos+1, 2*n) - 1ll*rr[pos]*t.getSz(1, 2*n, 1, pos+1, 2*n); long long yy = 1ll*rr[pos]*t.getSz(1, 2*n, 1, 1, pos-1) - t.get(1, 2*n, 1, 1, pos-1); f[1][i] = xx + yy; } if (k == 1) cout <<f[0][n] + ans + n; else { long long res = maxc; for (int i = 0; i <= n; i++) res = min(res, ans + f[0][i] + f[1][i+1] + n); cout <<res; } }
#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...