Submission

Score: 0

User: singtoppy

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

Language: cpp

Time: 0.002 second

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

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

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

int n, A[100005];

void solve () {
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> A[i];
	int l = 0, r = int(1e9 + 1);
	int mx = 0;
	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 = 0, r = int(1e9 + 1);
	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;
}