Submission #470073

#	Time	Username	Problem	Language	Result	Execution time	Memory
470073		solver1104	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	201 ms	10868 KiB

bridge

//#pragma warning( disable : 4996 )
#include <bits/stdc++.h>

//#pragma GCC target ("avx2")
//#pragma GCC optimization ("O3")
//#pragma GCC optimization ("unroll-loops")

using namespace std;

int N, K, temp1, temp2;
char tmp1, tmp2;
const int INTMAX = 2147483647;

int main()
{
	/*
	string problemName = "";
	ifstream fin(problemName + ".in");
	ofstream fout(problemName + ".out");
	*/

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> K >> N;

	if (K == 1) {
		bool changedr = false;
		bool changedl = false;
		long long int sum = 0;
		multiset<int>::iterator lmedian;
		multiset<int>::iterator rmedian;
		long long int cursumleft = 0;
		long long int cursumright = 0;
		long long int curmin = INTMAX;
		int intervalnum = 0;
		vector<pair<int, pair<int, int>>> intervals;
		multiset<int> significantleft;
		multiset<int> significantright;
		for (int i = 0; i < N; i++) {
			cin >> tmp1 >> temp1 >> tmp2 >> temp2;
			if (tmp1 == tmp2) {
				sum += abs(temp2 - temp1);
			}
			else {
				sum++;
				intervalnum++;
				if (temp1 > temp2) {
					swap(temp1, temp2);
				}
				intervals.push_back({ temp1 + temp2, {temp1, temp2} });
				significantright.insert(temp1);
				significantright.insert(temp2);
			}
		}
		if (intervals.size()) {
			sort(intervals.begin(), intervals.end());
			rmedian = next(significantright.begin(), intervalnum);
			for (const int& i : significantright) {
				cursumright += abs(i - *rmedian);
			}
			curmin = cursumright;

			cout << curmin + sum;

		}
		else {
			cout << sum;
		}
	}
	else {
		bool changedr = false;
		bool changedl = false;
		long long int sum = 0;
		multiset<int>::iterator lmedian;
		multiset<int>::iterator rmedian;
		long long int cursumleft = 0;
		long long int cursumright = 0;
		long long int curmin = INTMAX;
		int intervalnum = 0;
		vector<pair<int, pair<int, int>>> intervals;
		multiset<int> significantleft;
		multiset<int> significantright;
		for (int i = 0; i < N; i++) {
			cin >> tmp1 >> temp1 >> tmp2 >> temp2;
			if (tmp1 == tmp2) {
				sum += abs(temp2 - temp1);
			}
			else {
				sum++;
				intervalnum++;
				if (temp1 > temp2) {
					swap(temp1, temp2);
				}
				intervals.push_back({ temp1 + temp2, {temp1, temp2} });
				significantright.insert(temp1);
				significantright.insert(temp2);
			}
		}
		if (intervals.size()) {
			sort(intervals.begin(), intervals.end());
			rmedian = next(significantright.begin(), intervalnum);
			for (const int& i : significantright) {
				cursumright += abs(i - *rmedian);
			}
			curmin = cursumright;

			temp1 = intervals[0].second.first;
			temp2 = intervals[0].second.second;
			significantleft.insert(temp1);
			significantleft.insert(temp2);
			if (significantright.lower_bound(temp2) == rmedian) {
				changedr = true;
				rmedian++;
			}
			significantright.erase(significantright.lower_bound(temp1));
			significantright.erase(significantright.lower_bound(temp2));

			lmedian = next(significantleft.begin(), 1);
			cursumleft += (temp2 - temp1);
			cursumright -= (abs(*rmedian - temp2) + abs(*rmedian - temp1));
			if (temp2 <= *rmedian && !changedr) {
				rmedian++;
			}
			curmin = min(curmin, cursumleft + cursumright);

			for (int i = 1; i < floor(intervalnum / 2); i++) {
				changedr = false;
				temp1 = intervals[i].second.first;
				temp2 = intervals[i].second.second;
				significantleft.insert(temp1);
				significantleft.insert(temp2);
				if (significantright.lower_bound(temp2) == rmedian) {
					changedr = true;
					rmedian++;
				}
				significantright.erase(significantright.lower_bound(temp1));
				significantright.erase(significantright.lower_bound(temp2));
				cursumleft += (abs(*lmedian - temp2) + abs(*lmedian - temp1));

				if (temp1 >= *lmedian) {
					lmedian++;
				}

				cursumright -= (abs(*rmedian - temp2) + abs(*rmedian - temp1));

				if (temp2 <= *rmedian && !changedr) {
					rmedian++;
				}

				curmin = min(curmin, cursumleft + cursumright);
			}

			cout << curmin + sum;

		}
		else {
			cout << sum;
		}
	}
}

Compilation message (stderr)

bridge.cpp: In function 'int main()':
bridge.cpp:28:8: warning: unused variable 'changedr' [-Wunused-variable]
   28 |   bool changedr = false;
      |        ^~~~~~~~
bridge.cpp:29:8: warning: unused variable 'changedl' [-Wunused-variable]
   29 |   bool changedl = false;
      |        ^~~~~~~~
bridge.cpp:33:17: warning: unused variable 'cursumleft' [-Wunused-variable]
   33 |   long long int cursumleft = 0;
      |                 ^~~~~~~~~~
bridge.cpp:73:8: warning: unused variable 'changedl' [-Wunused-variable]
   73 |   bool changedl = false;
      |        ^~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 32
• Subtask 5: 0 / 37