#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 = (valuex.size()>0?(i64)1e18 : 0);
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;
assert(k==1);
// 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 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
1 ms |
2524 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
2392 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 3 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 4 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2396 KB |
Output is correct |
| 7 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 8 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 9 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 10 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 11 |
Correct |
1 ms |
2396 KB |
Output is correct |
| 12 |
Correct |
15 ms |
7112 KB |
Output is correct |
| 13 |
Correct |
47 ms |
8884 KB |
Output is correct |
| 14 |
Correct |
28 ms |
7112 KB |
Output is correct |
| 15 |
Correct |
27 ms |
6092 KB |
Output is correct |
| 16 |
Correct |
19 ms |
8140 KB |
Output is correct |
| 17 |
Correct |
29 ms |
8640 KB |
Output is correct |
| 18 |
Correct |
40 ms |
8388 KB |
Output is correct |
| 19 |
Correct |
44 ms |
8656 KB |
Output is correct |
| 20 |
Correct |
19 ms |
8128 KB |
Output is correct |
| 21 |
Correct |
43 ms |
8384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4696 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
4700 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
