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;
typedef long long ll;
ll k, n;
ll s, t, numLeft, numRight, distFrom0;
ll minSum;
char p, q;
vector<pair<ll, ll> > events, eventss;
ll solveProblem() {
// cout << "Solving problem:\n";
sort(events.begin(), events.end());
ll prevLocation = 0;
ll finAns = 1000000000000000;
if (events.size() == 0)
{
finAns = minSum;
}
// cout << "Entering for loop\n";
for (int i = 0; i < events.size(); i++)
{
ll currLocation = events[i].first;
distFrom0 -= numRight * (currLocation - prevLocation);
distFrom0 += numLeft * (currLocation - prevLocation);
if (events[i].second == -1)
{
numRight--;
}
else
{
numLeft++;
}
finAns = min(finAns, minSum + 2 * distFrom0);
//cout << "At location " << currLocation << " dist is " << distFrom0 << '\n';
prevLocation = currLocation;
}
//cout << "Solved problem\n";
return finAns;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> k >> n;
minSum = 0;
numLeft = numRight = distFrom0 = 0;
if (k == 1)
{
for (int i = 0; i < n; i++)
{
cin >> p >> s >> q >> t;
if (p == q)
{
minSum += abs(t - s);
}
else
{
minSum += 1 + abs(t - s);
ll b = max(t, s);
ll a = min(t, s);
events.push_back({a, -1});
events.push_back({b, 1});
numRight++;
distFrom0 += a;
}
}
//cout << "Min sum is " << minSum << "\n";
//cout << "Initial dist: " << distFrom0 << "\n";
sort(events.begin(), events.end());
ll prevLocation = 0;
ll finAns = 1000000000000000;
if (events.size() == 0)
{
finAns = minSum;
}
for (int i = 0; i < events.size(); i++)
{
ll currLocation = events[i].first;
distFrom0 -= numRight * (currLocation - prevLocation);
distFrom0 += numLeft * (currLocation - prevLocation);
if (events[i].second == -1)
{
numRight--;
}
else
{
numLeft++;
}
finAns = min(finAns, minSum + 2 * distFrom0);
//cout << "At location " << currLocation << " dist is " << distFrom0 << '\n';
prevLocation = currLocation;
}
cout << finAns << "\n";
return 0;
}
for (int i = 0; i < n; i++)
{
//cout << "This i = " << i << "\n";
cin >> p >> s >> q >> t;
if (p == q)
{
minSum += abs(t - s);
}
else
{
minSum += 1 + abs(t - s);
ll b = max(t, s);
ll a = min(t, s);
eventss.push_back({a, b});
}
}
//cout << "Checking size\n";
if(eventss.size() < 2) {
cout << minSum << "\n";
return 0;
}
ll finAns = 1000000000000000;
//cout << "Eventss size: " << eventss.size() << "\n";
for (int i = 0; i < eventss.size(); i++)
{
// cout << "i = " << i << "\n";
distFrom0 = numLeft = numRight = 0;
events.clear();
for (int j = 0; j < eventss.size(); j++)
{
// cout << "j1 = " << j << "\n";
if (eventss[j].second < eventss[i].first or eventss[j].first > eventss[i].first)
{
//cout << "In if\n";
events.push_back({eventss[j].first, -1});
events.push_back({eventss[j].second, 1});
distFrom0 += eventss[j].first;
numRight++;
}
}
finAns = min(finAns, solveProblem());
distFrom0 = numLeft = numRight = 0;
events.clear();
for (int j = 0; j < eventss.size(); j++)
{
if (eventss[j].second < eventss[i].second or eventss[j].first > eventss[i].second)
{
events.push_back({eventss[j].first, -1});
events.push_back({eventss[j].second, 1});
distFrom0 += eventss[j].first;
numRight++;
}
}
finAns = min(finAns, solveProblem());
}
cout << finAns << "\n";
}
Compilation message (stderr)
bridge.cpp: In function 'll solveProblem()':
bridge.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < events.size(); i++)
| ~~^~~~~~~~~~~~~~~
bridge.cpp: In function 'int main()':
bridge.cpp:79:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for (int i = 0; i < events.size(); i++)
| ~~^~~~~~~~~~~~~~~
bridge.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < eventss.size(); i++)
| ~~^~~~~~~~~~~~~~~~
bridge.cpp:127:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | for (int j = 0; j < eventss.size(); j++)
| ~~^~~~~~~~~~~~~~~~
bridge.cpp:142:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | for (int j = 0; j < eventss.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... |