| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 263282 | Kastanda | Palembang Bridges (APIO15_bridge) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// M
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 100005 * 2;
int n, k, ID[N];
ll dp[N], FA[N], FB[N], FC[N];
pair < ll , ll > FL[N], FR[N];
pair < int , int > A[N];
vector < int > U, V, S[N], E[N];
inline void AddFen(int i, int a, int b, int c)
{
for (i ++; i < N; i += i & - i)
FA[i] += a, FB[i] += b, FC[i] += c;
}
inline void AddFen(int l, int r, int a, int b, int c)
{
AddFen(l, a, b, c);
AddFen(r, -a, -b, -c);
}
inline vector < ll > GetFen(int i)
{
vector < ll > rt = {0, 0, 0};
for (i ++; i; i -= i & - i)
rt[0] += FA[i], rt[1] += FB[i], rt[2] += FC[i];
return rt;
}
inline void Add(int i, int val)
{
// [0, ID[i]] , -U[A[i]].y , .x , .y
AddFen(0, ID[i] + 1, -U[A[i].y] * val, 0, 1 * val);
// [ID[i] + 1, N) U[A[i].x]
AddFen(ID[i] + 1, N, U[A[i].x] * val, -1 * val, 0);
}
inline ll Query(int a, int b)
{
ll rt = 0;
rt += FL[a].x + FL[a].y * (ll)U[a];
rt += FR[b].x + FR[b].y * (ll)U[b];
int lb = upper_bound(V.begin(), V.end(), U[a] + U[b]) - V.begin() - 1;
vector < ll > tmp = GetFen(lb);
rt += tmp[0];
rt += tmp[1] * (ll)U[a];
rt += tmp[2] * (ll)U[b];
return rt;
}
void Solve(int l, int r, int le, int ri)
{
if (r < l)
return ;
int md = (l + r) >> 1, opt = -1;
// [le, l) is added ...
// Extending from right to [le, md]
for (int i = l; i <= md; i ++)
for (int j : E[i])
if (A[j].x >= le) // Should be added
Add(j, 1);
// [le, md] is added, time for querying ..
dp[md] = (ll)(1e18);
for (int i = le; i <= min(ri, md); i ++)
{
ll val = Query(i, md);
if (dp[md] >= val)
dp[md] = val, opt = i;
// Shrinking from left to [i + 1, md]
for (int j : S[i])
if (A[j].y <= md) // Should be deleted
Add(j, -1);
}
// Now we have [min(ri, md) + 1, md]
// Extending from left to [opt, md]
for (int i = min(ri, md); i >= opt; i --)
for (int j : S[i])
if (A[j].y <= md) // Should be added
Add(j, 1);
Solve(md + 1, r, opt, ri);
// Extending from left to [le, md]
for (int i = opt - 1; i >= le; i --)
for (int j : S[i])
if (A[j].y <= md)
Add(j, 1);
// Shrinking from right to [le, l)
for (int i = md; i >= l; i --)
for (int j : E[i])
if (A[j].x >= le)
Add(j, -1);
Solve(l, md - 1, le, opt);
}
int main()
{
ll SM = 0;
cin >> k >> n;
for (int i = 1; i <= n; i ++)
{
int a, b;
//char sa[1], sb[1];
string sa, sb;
//scanf("%s%d%s%d", sa, &a, sb, &b);
cin >> sa >> a >> sb >> b;
if (a > b) swap(a, b);
SM += b - a;
if (sa[0] == sb[0])
{n --; i --; continue;}
SM ++;
A[i] = {a, b};
U.push_back(a);
U.push_back(b);
V.push_back(a + b);
}
if (!n)
return !printf("%lld\n", SM);
sort(U.begin(), U.end());
U.resize(unique(U.begin(), U.end()) - U.begin());
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
for (int i = 1; i <= n; i ++)
{
ID[i] = (int)(lower_bound(V.begin(), V.end(), A[i].x + A[i].y) - V.begin());
A[i].x = (int)(lower_bound(U.begin(), U.end(), A[i].x) - U.begin());
A[i].y = (int)(lower_bound(U.begin(), U.end(), A[i].y) - U.begin());
S[A[i].x].push_back(i);
E[A[i].y].push_back(i);
}
for (int i = 0; i < (int)U.size(); i ++)
{
// Sum of .y for all .y <= U[i]
if (i)
FL[i] = FL[i - 1];
for (int j : E[i])
FL[i].x -= U[i], FL[i].y ++;
}
for (int i = (int)U.size() - 1; ~ i; i --)
{
// Sum of .x for all .x >= U[i]
FR[i] = FR[i + 1];
for (int j : S[i])
FR[i].x += U[i], FR[i].y --;
}
ll Mn = (ll)(1e18);
for (int i = 0; i < (int)U.size(); i ++)
{
ll rt = 0;
rt += FL[i].x + FL[i].y * (ll)U[i];
rt += FR[i].x + FR[i].y * (ll)U[i];
Mn = min(Mn, rt);
}
if (k == 1)
return !printf("%lld\n", Mn * 2LL + SM);
/*for (int a : U)
printf("%d ", a);
printf("\n");
for (int i = 1; i <= n; i ++)
printf("(%d %d) ", A[i].x, A[i].y);
printf("\n");*/
/*for (int i = 0; i < (int)U.size(); i ++)
{
dp[i] = (ll)(1e18);
for (int j = i; j >= 0; j --)
{
for (int h : S[j])
if (A[h].y <= i)
Add(h, 1);
ll val = Query(j, i);
if (dp[i] >= val)
dp[i] = val;
}
for (int j = 0; j <= i; j ++)
{
for (int h : S[j])
if (A[h].y <= i)
Add(h, -1);
}
}*/
for (int i = 0; i < (int)U.size(); i ++)
{
dp[i] = (ll)(1e18);
for (int j = 0; j <= i; j ++)
{
ll sm = 0;
for (int h = 1; h <= n; h ++)
{
if (A[h].y <= j)
sm += U[j] - U[A[h].y];
else if (A[h].x >= i)
sm += U[A[h].x] - U[i];
else if (A[h].x > j && A[h].y < i)
{
if (U[j] + U[i] <= U[A[h].x] + U[A[h].y])
sm += min(U[i] - U[A[h].y]);
else
sm += min(U[A[h].x] - U[j]);
//sm += min(U[i] - U[A[h].y], U[A[h].x] - U[j]);
}
}
dp[i] = min(dp[i], sm);
}
}
/*for (int i = 0; i < (int)U.size(); i ++)
printf("%lld ", dp[i]);
printf("\n");*/
//Solve(0, (int)U.size() - 1, 0, (int)U.size() - 1);
for (int i = 0; i < (int)U.size(); i ++)
Mn = min(Mn, dp[i]);
return !printf("%lld\n", Mn * 2LL + SM);
}