Submission #43681

#	Time	Username	Problem	Language	Result	Execution time	Memory
43681		RezwanArefin01	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2 ms	508 KiB

bridge

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

struct ds {
	vector<int> a; 
	vector<ll> s;
	void add(int x) { a.push_back(x); }
	void init() { 
		sort(a.begin(), a.end()); 
		s.resize(a.size()); 
		s[0] = a[0];
		for(int i = 1; i < a.size(); i++) {
			s[i] = s[i - 1] + a[i]; 
		}
	}
	ll get(ll x) {
		int lo = 0, hi = a.size() - 1, idx = -1;
		while(lo <= hi) {
			int mid = lo + hi >> 1; 
			if(a[mid] <= x) idx = mid, lo = mid + 1;
			else hi = mid - 1; 
		}
		if(idx == -1) {
			return s[a.size() - 1] - a.size() * x;
		} else {
			ll ret = x * (idx + 1) - s[idx]; 
			ret += s[a.size() - 1] - s[idx] - (a.size() - 1 - idx) * x; 
			return ret; 
		}
	}
} A, B; 

int main(int argc, char const *argv[]) {
#ifdef LOCAL_TESTING
	freopen("in", "r", stdin);
#endif
	int k, n; cin >> k >> n; if(k != 1) return 0;
	vector<int> pos; 
	ll ans = 0;
	for(int i = 0; i < n; i++) {
		char p, q; int t, s; 
		cin >> p >> s >> q >> t; 
		if(p == q) ans += abs(s - t); 
		else {
			A.add(s), B.add(t);
			pos.push_back(s);
			pos.push_back(t); 
		}
	}
	A.init(); B.init();

//	sort(pos.begin(), pos.end());
//	pos.erase(unique(pos.begin(), pos.end()), pos.end());

	ll Min = 1e18;

	for(int p : pos) {
		Min = min(Min, A.get(p) + B.get(p)); 
	}
	cout << Min + A.a.size() + ans << endl;

}

Compilation message (stderr)

bridge.cpp: In member function 'void ds::init()':
bridge.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 1; i < a.size(); i++) {
                    ^
bridge.cpp: In member function 'll ds::get(ll)':
bridge.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid = lo + hi >> 1; 
                 ^

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