| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1053613 | _rain_ | Palembang Bridges (APIO15_bridge) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define prev t1vodich
#define prefix orzhehe
const int maxn = 1e5;
i64 prev1[maxn+2] , suf1[maxn+2];
i64 prev2[maxn+2] , suf2[maxn+2];
int n , k;
struct Point
{
char zone1 , zone2;
int p1 , p2;
void read()
{
cin>>zone1>>p1>>zone2>>p2;
if (p1>p2) {
swap(p1,p2);
swap(zone1,zone2);
}
return;
}
};
Point point[maxn+2];
namespace subtask1
{
bool check()
{
return k == 1;
}
vector<int> v1 , v2;
i64 prefixA(int l , int r)
{
if (l>r) return 0;
return prev1[r] - prev1[l - 1];
}
i64 prefixB(int l , int r)
{
if (l>r) return 0;
return prev2[r] - prev2[l - 1];
}
i64 sufA(int l , int r)
{
if (l>r) return 0;
return suf1[l] - suf1[r+1];
}
i64 sufB(int l , int r)
{
if (l>r) return 0;
return suf2[l] - suf2[r+1];
}
i64 length(int l , int r)
{
if (l>r) return 0;
return r - l + 1;
}
i64 getA(int x)
{
int xx = upper_bound(v1.begin(),v1.end(),x) - v1.begin() - 1;
int nwn = v1.size()-1;
return (i64)x * length(1,xx) - prefixA(1 , xx) + sufA(xx+1,nwn) - (i64)x * length(xx+1,nwn);
}
i64 getB(int x)
{
int xx = upper_bound(v2.begin(),v2.end(),x) - v2.begin() - 1;
int nwn = v2.size()-1;
return (i64)x * length(1,xx) - prefixB(1 , xx) + sufB(xx+1,nwn) - (i64)x * length(xx+1,nwn);
}
void main_code()
{
vector<int> valuex;
v1.push_back(-1); v2.push_back(-1);
i64 answer = 0;
for (int i = 1; i <= n; ++i)
{
if (point[i].zone1==point[i].zone2)
answer += point[i].p2 - point[i].p1;
else {
if (point[i].zone1=='A') v1.push_back(point[i].p1); else v2.push_back(point[i].p1);
if (point[i].zone2=='A') v1.push_back(point[i].p2); else v2.push_back(point[i].p2);
valuex.push_back(point[i].p1);
valuex.push_back(point[i].p2);
}
// cout << point[i].zone1 << ' ' << point[i].p1 << ' ' << point[i].zone2 << ' ' << point[i].p2 << '\n';
}
sort(valuex.begin(),valuex.end()); valuex.resize(unique(valuex.begin(),valuex.end())-valuex.begin());
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
for (int i = 1; i < v1.size(); ++i)
prev1[i]=prev1[i-1]+v1[i];
for (int i = v1.size()-1; i >= 1; --i)
suf1[i]=suf1[i+1]+v1[i];
for (int i = 1; i < v2.size(); ++i)
prev2[i]=prev2[i-1]+v2[i];
for (int i = v2.size()-1;i >= 1; --i)
suf2[i]=suf2[i+1]+v2[i];
i64 addmore = (i64)1e18;
for (auto& x : valuex)
{
addmore = min(addmore , getA(x) + getB(x) + v1.size() - 1);
// cout << x << ' ' << getA(x) + getB(x) + v1.size() - 1 << '\n';;
}
cout << addmore + answer << '\n';
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#define name "main"
if (fopen(name".inp","r"))
{
freopen(name".inp","r",stdin);
freopen(name".out","w",stdout);
}
cin >> k >> n;
for (int i = 1; i <= n; ++i) point[i].read();
if (subtask1::check()) return subtask1::main_code(),0;
// if (subtask2::check()) return subtask2::main_code(),0;
}