Submission #469777

#	Time	Username	Problem	Language	Result	Execution time	Memory
469777		solver1104	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	1 ms	204 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<int, int>> significant;
		long long int sum = 0;
		int intervalnum = 0;
		int starting;
		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 if (temp1 == temp2) {
				sum += 1;
			}
			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;
		for (int i = 1; i < 2 * intervalnum; i++) {
			curmin = min(cursum, curmin);
			if (significant[i].first != significant[i - 1].first) {
				cursum += 2 * (significant[i].first - significant[i - 1].first) * (ending - starting);
			}
			if (significant[i].second) {
				ending++;
			}
			if (!significant[i].second) {
				starting--;
			}
		}
		curmin = min(curmin, cursum);
		cout << curmin + sum;
	}
	else {

	}
}

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