#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
bool compare(pair<int,int> a, pair<int,int> b) {
if (a.first == b.first) {
return a.second > b.second;
}
return a.first < b.first;
}
int32_t main() {
char p, q;
int s, t, k, n; cin >> k >> n;
ll ans = 0;
unordered_map<int,int> bruh;
unordered_map<int,int> sus;
vector<int> bridgeplaces;
vector<pair<int, int>> housework;
if (k == 2) {
ll baseans = 0;
for (int i=0;i<n;i++) {
cin >> p >> s >> q >> t;
if (p == q) {
baseans += abs(s - t);
continue;
}
if (t > s) {
swap(t, s);
}
housework.push_back(make_pair(s + t, s - t));
}
n = housework.size();
unordered_set<int> posset;
pair<int,int> dum;
vector<int> posplaces;
for (int i=0;i<n;i++) {
if (posset.find((housework[i].first - housework[i].second) / 2) == posset.end()) {
posset.insert((housework[i].first - housework[i].second) / 2);
posplaces.push_back((housework[i].first - housework[i].second) / 2);
}
if (posset.find((housework[i].first + housework[i].second) / 2) == posset.end()) {
posset.insert((housework[i].first + housework[i].second) / 2);
posplaces.push_back((housework[i].first + housework[i].second) / 2);
}
}
while (true) {}
sort(posplaces.begin(), posplaces.end());
sort(housework.begin(), housework.end(), compare);
while (true) {}
vector<int> ansright(n-1), ansleft(n-1);
priority_queue<int, vector<int>, greater<int>> lefttown, righttown;
while (true) {}
ll ahead = 0, behind = 0, curpos = 0, sigma, tate; ans = 0;
for (int i=0;i<n-1;i++) {
if (curpos >= posplaces.size()) {
while (true) {}
}
ans += housework[i].second + 1;
sigma = (housework[i].first - housework[i].second) / 2;
tate = (housework[i].first + housework[i].second) / 2;
if (sigma > posplaces[curpos]) {
ahead++;
ans += 2 * (sigma - posplaces[curpos]);
lefttown.push(sigma);
}
if (tate == posplaces[curpos]) {
behind++;
} else {
righttown.push(tate);
}
while (ahead > behind) {
curpos++;
if (curpos >= posplaces.size()) {
while (true) {}
}
ans -= 2*(ahead - behind)*(posplaces[curpos] - posplaces[curpos - 1]);
while (!lefttown.empty() && lefttown.top() == posplaces[curpos]) {
lefttown.pop();
ahead--;
}
while (!righttown.empty() && righttown.top() == posplaces[curpos]) {
righttown.pop();
behind++;
}
}
//cout << posplaces[curpos] << '\n';
ansleft[i] = ans;
}
priority_queue<int> lefttown2, righttown2;
ahead = 0; behind = 0; curpos = posplaces.size() - 1; ans = 0;
for (int i=n-1;i>0;i--) {
ans += housework[i].second + 1;
sigma = (housework[i].first - housework[i].second) / 2;
tate = (housework[i].first + housework[i].second) / 2;
if (tate < posplaces[curpos]) {
ahead++;
ans += 2 * (posplaces[curpos] - tate);
righttown2.push(tate);
}
if (sigma == posplaces[curpos]) {
behind++;
} else {
lefttown.push(sigma);
}
lefttown2.push(sigma);
while (ahead > behind) {
curpos--;
ans -= 2*(ahead - behind)*(posplaces[curpos + 1] - posplaces[curpos]);
while (!righttown2.empty() && righttown2.top() == posplaces[curpos]) {
righttown2.pop();
ahead--;
}
while (!lefttown2.empty() && lefttown2.top() == posplaces[curpos]) {
lefttown2.pop();
behind++;
}
}
ansright[i - 1] = ans;
}
//for (int i=0;i<n-1;i++) {
// cout << ansright[i] << ' ';
//} cout << '\n';
//for (int i=0;i<n-1;i++) {
// cout << ansleft[i] << ' ';
//} cout << '\n';
ll realans = INT64_MAX;
for (int i=0;i<n-1;i++) {
realans = min(realans, ansleft[i] + ansright[i]);
}
cout << realans + baseans;
return 0;
}
ll ahead = 0;
for (int i=0;i<n;i++) {
cin >> p >> s >> q >> t;
if (t > s) {
swap(t, s);
}
if (p == q) {
ans += abs(s - t);
continue;
}
ahead++;
housework.push_back(make_pair(t, s));
if (bruh.find(s) == bruh.end()) {
bruh[s] = 1;
if (sus.find(s) == sus.end()) {
bridgeplaces.push_back(s);
}
} else {
bruh[s]++;
}
if (sus.find(t) == sus.end()) {
sus[t] = 1;
if (bruh.find(t) == bruh.end()) {
bridgeplaces.push_back(t);
}
} else {
sus[t]++;
}
}
sort(bridgeplaces.begin(), bridgeplaces.end());
for (pair<int,int> i: housework) {
ans += i.first + i.second + 1;
}
ll curans = ans;
ll prev = 0;
ll visitednum = 0;
for (int i=0;i<bridgeplaces.size();i++) {
curans += 2 * (bridgeplaces[i] - prev) * (visitednum - ahead);
//cout << visitednum << ' ' << ahead << ' ' << bridgeplaces[i] << ' ' << curans << '\n';
if (bruh.find(bridgeplaces[i]) != bruh.end()) {
visitednum += bruh[bridgeplaces[i]];
}
if (sus.find(bridgeplaces[i]) != sus.end()) {
ahead -= sus[bridgeplaces[i]];
}
ans = min(ans, curans);
prev = bridgeplaces[i];
}
cout << ans;
}
Compilation message
bridge.cpp: In function 'int32_t main()':
bridge.cpp:65:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | if (curpos >= posplaces.size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:83:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | if (curpos >= posplaces.size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
bridge.cpp:191:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for (int i=0;i<bridgeplaces.size();i++) {
| ~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
2 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
2 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
1 ms |
348 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
448 KB |
Output is correct |
| 12 |
Correct |
27 ms |
3280 KB |
Output is correct |
| 13 |
Correct |
116 ms |
14656 KB |
Output is correct |
| 14 |
Correct |
39 ms |
4560 KB |
Output is correct |
| 15 |
Correct |
67 ms |
8540 KB |
Output is correct |
| 16 |
Correct |
46 ms |
3780 KB |
Output is correct |
| 17 |
Correct |
104 ms |
14824 KB |
Output is correct |
| 18 |
Correct |
73 ms |
14104 KB |
Output is correct |
| 19 |
Correct |
113 ms |
14616 KB |
Output is correct |
| 20 |
Correct |
50 ms |
3780 KB |
Output is correct |
| 21 |
Correct |
88 ms |
14364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2040 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2005 ms |
344 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
