Submission #831731

#	Time	Username	Problem	Language	Result	Execution time	Memory
831731		serifefedartar	Palembang Bridges (APIO15_bridge)	C++17	0 / 100	1 ms	340 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 1000000007
#define LOGN 18
#define MAXN 200005

vector<ll> prefleftV, prefrightV;
vector<ll> leftV, rightV;
ll calc(int mid) {
	int L = mid+1;
}

ll get(ll mid) {
	ll from_left = upper_bound(rightV.begin(), rightV.end(), mid) -  rightV.begin();
	ll from_right = upper_bound(leftV.begin(), leftV.end(), mid) - leftV.begin();
	ll sum_left = prefrightV[from_left];
	ll sum_right = prefleftV.back() - prefleftV[from_right];
	ll res = mid * from_left - sum_left + sum_right - mid * (prefleftV.size() - from_right - 1);
	return res;
}

int main() {
	fast
	ll K, N;
	cin >> K >> N;

	ll sum = 0;
	for (int i = 0; i < N; i++) {
		char ch1, ch2;
		ll pos1, pos2;
		cin >> ch1 >> pos1 >> ch2 >> pos2;	

		if (ch1 == ch2)
			sum += abs(pos2 - pos1);
		else {
			sum += abs(pos1 - pos2) + 1;
			leftV.push_back(min(pos1, pos2));
			rightV.push_back(max(pos1, pos2));
		}
	}
	sort(leftV.begin(), leftV.end());
	sort(rightV.begin(), rightV.end());
	prefleftV = vector<ll>(leftV.size()+1, 0);
	prefrightV = vector<ll>(rightV.size()+1, 0);
	for (int i = 0; i < leftV.size(); i++)
		prefleftV[i+1] = prefleftV[i] + leftV[i];
	for (int i = 0; i < rightV.size(); i++)
		prefrightV[i+1] = prefrightV[i] + rightV[i];

	if (K == 1) {
		int L = 0;
		int R = 1000000001;
		while (R-L > 1) {
			int mid = L + (R-L)/2;
			if (get(mid) < get(mid+1))
				R = mid;
			else
				L = mid;
		}
		cout << 2*get((L+R)/2) + sum << "\n";
	} else {
		int L = 0;
		int R = 1000000001;
		while (L <= R) {
			int m1 = L + (R-L)/3;
			int m2 = R - (R-L)/3;
			if (calc(m1) < calc(m2))
				L = m1;
			else
				R = m2;
		}
		cout << calc(L) << "\n";
	}
}

Compilation message (stderr)

bridge.cpp: In function 'll calc(int)':
bridge.cpp:15:6: warning: unused variable 'L' [-Wunused-variable]
   15 |  int L = mid+1;
      |      ^
bridge.cpp:16:1: warning: no return statement in function returning non-void [-Wreturn-type]
   16 | }
      | ^
bridge.cpp: In function 'int main()':
bridge.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < leftV.size(); i++)
      |                  ~~^~~~~~~~~~~~~~
bridge.cpp:52:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for (int i = 0; i < rightV.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~

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