Submission

Score: 0

User: singtoppy

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

Language: cpp

Time: 0.003 second

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

#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));
	cin >> n;
	for(int i = 0; i < n; i++) {
		cin >> A[i];
		freq[A[i]]++;
	}
	int l = 1, r = int(1e9), mx1 = 0, mx2 = 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 < mx1) 
			r = mid;
		else {
			mx1 = 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 < mx2)
			l = mid + 1;
		else {
			mx2 = cnt;
			r = mid;
		}
	}
	int mx3 = 0;
	for(int i = 0; i < n; i++) 
		mx3 = max(mx3, freq[A[i]]);
	cout << max({mx1, mx2, mx3});
}

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

	solve();

	return 0;
}