#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)
{
i64 xx = getA(x) + getB(x) + v1.size() - 1;
addmore = min(addmore , xx);
}
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;
}
Compilation message
bridge.cpp: In function 'void subtask1::main_code()':
bridge.cpp:93:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for (int i = 1; i < v1.size(); ++i)
| ~~^~~~~~~~~~~
bridge.cpp:97:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 1; i < v2.size(); ++i)
| ~~^~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:118:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | freopen(name".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridge.cpp:119:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | freopen(name".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
