Submission #33630

#	Time	Username	Problem	Language	Result	Execution time	Memory
33630		sinhriv	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	83 ms	6744 KiB

bridge

#include <bits/stdc++.h>

using namespace std;

struct Point{
	int x;
	int y;

	void read(){
		char read[5];
		scanf("%s%d", read, &y);
		x = (read[0] - 'A');
	}
};	

struct Person{
	Point u;
	Point v;

	bool check(){
		u.read();
		v.read();
		return (u.x == v.x);
	}

	int calc(int val){
		return abs(u.y - val) + abs(v.y - val);
	}
};

vector < pair < int, int > > a;

long long One(){
	if(a.size() == 0) return 0;
	int n = a.size();
	vector < int > lst;

	for(int i = 0; i < n; ++i){
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);
	}

	sort(lst.begin(), lst.end());

	long long ans = 0;


	for(int i = 0; i < n + n; ++i){
		ans += abs(lst[i] - lst[n]);
	}
	return ans + n; 
}

struct lex_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.first + x.second == y.first + y.second) {
  		if(x.first == y.first) return x.second < y.second;
  		return x.first < y.first;
  	}
  	return x.first + x.second < y.first + y.second;
  }
};


struct second_compare {
  bool operator() (const pair < int, int >& x, const pair < int, int >&y) const {
  	if(x.second != y.second) return x.second  < y.second;
  	return x.first < y.first;
  }
};

const int N = 2e5 + 10;

long long prefix[N];

int calc(pair < int, int > p, int val){
	return abs(p.first - val) + abs(p.second - val);
}

long long Two(){
	int n = a.size();
	if(n == 0) return 0;

	vector < int > lst;

	for(int i = 0; i < n; ++i){
		if(a[i].first > a[i].second){
			swap(a[i].first, a[i].second);
		}
		lst.push_back(a[i].first);
		lst.push_back(a[i].second);

	}

	sort(a.begin(), a.end());
	sort(lst.begin(), lst.end());
	lst.resize(unique(lst.begin(), lst.end()) - lst.begin());

	for(int i = 0; i < n; ++i){
		prefix[i] = a[i].first + a[i].second;
		if(i > 0) prefix[i] += prefix[i - 1];
	}

	int small = 0;

	long long sum = 0;
	long long total = 0;
	
	long long ans = 1e18;

	multiset < int > tree;



	for(int i = 0; i < lst.size(); ++i){
		int x = lst[i];
		while(small < n && a[small].first <= x){
			sum += a[small].second;
			total += a[small].first;
			tree.insert(a[small].second);
			++small;
		}
		while(!tree.empty() && *tree.begin() <= x){
			sum -= *tree.begin() * 2;
			tree.erase(tree.begin());
		}


		long long now = (1LL * small * x - total) + (sum + 1LL * (small - 2 * tree.size()) * x);
	
		multiset < pair < int, int >, lex_compare > inside;	
		multiset < pair < int, int >, second_compare > big;
		
		long long sumBig = 0;
		long long sumInside = 0;
		long long sumOutside = 0;

		int pter = small;		
		for(int j = i + 1; j < lst.size(); ++j){
			int y = lst[j];
			int where = lower_bound(a.begin(), a.end(), make_pair(y, 0)) - a.begin();

			long long most = prefix[n - 1] - (where > 0 ? prefix[where - 1] : 0) - 2LL * (n - where) * y;

			
			while(pter < where){
				if(a[pter].second >= y){
					big.insert(a[pter]);
					sumBig += calc(a[pter], y);
				}
				else{
					inside.insert(a[pter]);
					sumInside += calc(a[pter], y);
				}
				++pter;
			}
			
			while(!big.empty() && big.begin() -> second < y){
				sumBig -= calc(*big.begin(), y);
				sumInside += calc(*big.begin(), y);
				inside.insert(*big.begin());
				big.erase(big.begin());
			}

			while(!inside.empty()){
				auto p = *inside.begin();
				if(p.first + p.second <= x + y){
					sumInside -= calc(p, y);
					sumOutside += calc(p, x);
					inside.erase(inside.begin());
					continue;
				}
				break; 
			}

			ans = min(ans, sumInside + sumOutside + sumBig + most + now);
		}
	}

	return n + ans;
}

int main(){
	if(fopen("1.inp", "r")){
		freopen("1.inp", "r", stdin);
	}

	long long out = 0;

	int k, n;
	scanf("%d%d", &k, &n);

	for(int i = 1; i <= n; ++i){
		Person x;
		if(x.check()){
			out += x.calc(x.u.y);
		}
		else{
			a.emplace_back(x.u.y, x.v.y);
		}
	}

	if(k == 1) cout << One() + out;
	else{
		cout << min(One(), Two()) + out;
	}
	return 0;
}

Compilation message (stderr)

bridge.cpp: In function 'long long int Two()':
bridge.cpp:115:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < lst.size(); ++i){
                   ^
bridge.cpp:139:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i + 1; j < lst.size(); ++j){
                        ^
bridge.cpp: In function 'int main()':
bridge.cpp:185:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("1.inp", "r", stdin);
                               ^
bridge.cpp:191:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &k, &n);
                       ^
bridge.cpp: In member function 'void Point::read()':
bridge.cpp:11:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d", read, &y);
                          ^

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