Submission #469762

#	Time	Username	Problem	Language	Result	Execution time	Memory
469762		solver1104	Palembang Bridges (APIO15_bridge)	C++11	0 / 100	1 ms	332 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;
		map<int,int> starts;
		map<int, int> ends;
		long long int sum = 0;
		int intervalnum = 0;
		int cpv = 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);
				
				starts[temp1]++;
				ends[temp2] ++;
				significant.push_back({ temp1, 0 });
				significant.push_back({ temp2, 1 });
			}
		}
		
		sort(significant.begin(), significant.end());
		cpv = significant[0].first;
		for (auto i : starts) {
			cursum += 2 * (i.first - cpv) * i.second;
		}
		ending = 0;
		starting = intervalnum - 1;
		for (int i = 1; i < 2 * intervalnum; i++) {
			curmin = min(cursum, curmin);
			cursum += 2 * (significant[i].first - significant[i - 1].first) * (ending - starting);
			if (significant[i].second) {
				ending ++;
			}
			else {
				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