# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1054177 | kiryl_krutsko | Palembang Bridges (APIO15_bridge) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>#include <vector>#include <cmath>using namespace std;struct way { int left, right; way(int n1, int n2) { left = min(n1, n2); right = max(n1, n2); }};int bs(int start, int end, vector<way>* vec, int start_ans) { int ans = start_ans; int right = 0; int left = 0; int mid = (start + end) / 2; //cout << mid << " : "; for (int i = 0; i < vec->size();i++) { way cur = vec->at(i); if (cur.right < mid) { ans += (mid - cur.right) * 2; left++; } else if (cur.left > mid) { ans += (cur.left - mid) * 2; right++; } else if (cur.left<start && cur.right>start) { vec->erase(vec->begin() + i); i--; } } //cout << left << " " << right << " " << endl << "ans : " << ans << endl; if (right == left || start == end) { //cout << mid << endl; return ans; } else if (right > left) { return bs(mid + 1, end, vec, start_ans); } else { return bs(start, mid, vec, start_ans); }}int main(){ int n, k, ans; cin >> k >> n; ans = 0; vector<way> vec; int n1, n2; char t1, t2; int max = 0; int min = 1000000001; for (int i = 0; i < n; i++) { cin >> t1 >> n1 >> t2 >> n2; ans += abs(n1 - n2); if (t1 != t2) { ans++; way w = way(n1, n2); if (w.left < min) min = w.left; if (w.right > max) max = w.right; vec.push_back(w); } } if (k == 1) { cout << bs(min, max, &vec, ans) << endl; }}