Submission #470071

#	Time	Username	Problem	Language	Result	Execution time	Memory
470071		solver1104	Palembang Bridges (APIO15_bridge)	C++11	22 / 100	52 ms	4548 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) {
		vector<pair<long long int, int>> significant;
		long long int sum = 0;
		int intervalnum = 0;
		long long int starting;
		long long int ending;
		long long int curmin = INTMAX;
		long long int cursum = 0;

		for (int i = 0; i < N; i++) {
			cin >> tmp1 >> temp1 >> tmp2 >> temp2;
			if (tmp1 == tmp2) {
				sum += abs(temp1 - temp2);
			}

			else {
				intervalnum++;
				if (temp1 > temp2) {
					swap(temp1, temp2);
				}
				sum += (1 + temp2 - temp1);

				significant.push_back({ temp1, 0 });
				significant.push_back({ temp2, 1 });
			}
		}

		sort(significant.begin(), significant.end());
		for (pair<int, int> i : significant) {
			if (!i.second) {
				cursum += (2 * (i.first - significant[0].first));
			}
		}
		ending = 0;
		starting = intervalnum - 1;
		curmin = cursum;
		for (int i = 1; i < 2 * intervalnum; i++) {
			if (significant[i].first != significant[i - 1].first) {
				cursum += 2 * (significant[i].first - significant[i - 1].first) * (ending - starting);
				curmin = min(cursum, curmin);
			}
			if (significant[i].second) {
				ending++;
			}
			else {
				starting--;
			}
		}
		curmin = min(curmin, cursum);
		cout << curmin + 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:80:8: warning: unused variable 'changedl' [-Wunused-variable]
   80 |   bool changedl = false;
      |        ^~~~~~~~

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