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>
#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair
#define int long long
using namespace std;
const int inf = (int)1e15 + 7;
const int N = (int)2e5 + 7;
int k,n;
int x,y;
int suma,sumb;
int pos,pos1;
int ca,cb;
int ans = inf,cur;
char ch,ch1;
vector <int> a,b,vec;
vector <pair<int,int> > vc;
int f (int x,int y) {
suma = 0;
for (int i = 0; i < (int)vc.size(); i ++)
suma += min((abs(vc[i].fr - x) + abs(vc[i].sc - x)),(abs(vc[i].fr - y) + abs(vc[i].sc - y)));
return (suma + cur + (int)a.size());
}
main () {
cin >> k >> n;
for (int i = 1; i <= n; i ++) {
cin >> ch >> x >> ch1 >> y;
if (ch == ch1) {
cur += abs(x - y);
}
else {
if (ch == 'A') a.pb(x),b.pb(y);
else b.pb(x),a.pb(y);
vec.pb(x);
vec.pb(y);
vc.pb({x,y});
}
}
vec.pb(0);
vec.pb(1e9);
sort (vec.begin(),vec.end());
vec.erase(unique(vec.begin(),vec.end()),vec.end());
sort (a.begin(),a.end());
sort (b.begin(),b.end());
if (k == 1) {
for (int i = 0; i < (int)a.size(); i ++)
suma += abs(a[i] - vec[0]),sumb += abs(b[i] - vec[0]);
for (int j = 0; j < (int)vec.size(); j ++) {
ans = min(ans,cur + suma + sumb + (int)a.size());
pos = upper_bound(a.begin(),a.end(),vec[j]) - a.begin();
suma -= (((int)a.size() - pos) * 1ll * (vec[j + 1] - vec[j]));
suma += (pos * 1ll * (vec[j + 1] - vec[j]));
pos = upper_bound(b.begin(),b.end(),vec[j]) - b.begin();
sumb -= (((int)b.size() - pos) * 1ll * (vec[j + 1] - vec[j]));
sumb += (pos * 1ll * (vec[j + 1] - vec[j]));
}
cout << ans << endl;
}
else {
for (int i = 0; i < vec.size(); i ++) {
for (int j = 0; j < vec.size(); j ++) {
if (i != j) {
ans = min(ans,f(vec[i],vec[j]));
}
}
}
cout << ans << endl;
}
}
/**
Sample 1
1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
Sample 2
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
1 3
A 0 B 0
A 1 B 1
A 1000000000 B 1000000000
**/
Compilation message (stderr)
bridge.cpp:35:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main () {
^
bridge.cpp: In function 'int main()':
bridge.cpp:77:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vec.size(); i ++) {
~~^~~~~~~~~~~~
bridge.cpp:78:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < vec.size(); j ++) {
~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |