Submission

Score: 0

User: singtoppy

Problemset: จุดตัดบนกราฟ

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-08 20:41:08

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

#define ll long long
#define pii pair<int, int>

int n, A[100005];
unordered_map<int, int> freq;

void solve () {
	freq.reserve(int(1e5));
	int mx = 0;
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> A[i];
		freq[A[i]]++;
		// mx = max(mx, freq[A[i]]);
	}
	int l = 1, r = int(1e9);
	while(l < r) { //try going up
		double mid = (l + r) / 2.0;
		// cout << mid << '\n';
		int cnt = 0;
		for(int i = 0; i < n - 1; i++) 
			if(min(A[i], A[i + 1]) < mid && mid < max(A[i + 1], A[i]))
				cnt++;
		if(cnt < mx) 
			r = mid;
		else {
			mx = cnt;
			l = mid + 1;
		}
	}
	l = 1, r = int(1e9);
	while(l < r) {
		double mid = (l + r) / 2.0;
		// cout << mid << '\n';
		int cnt = 0;
		for(int i = 0; i < n - 1; i++) 
			if(min(A[i], A[i + 1]) < mid && mid < max(A[i + 1], A[i]))
				cnt++;
		if(cnt < mx)
			l = mid + 1;
		else {
			mx = cnt;
			r = mid;
		}
	}
	cout << mx;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	

	solve();

	return 0;
}