oj.uz

Submission #43681

# Submission time Handle Problem Language Result Execution time Memory
43681 2018-03-19T14:50:30 Z RezwanArefin01 Palembang Bridges (APIO15_bridge) C++14
0 / 100
 2 ms 508 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 508 KB Output isn't correct
2 Halted 0 ms 0 KB -