Submission

Score: 0

User: Nay-O

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

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-09 22:10:37

#include<bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

priority_queue<pii, vector<pii>,greater<pii>> pq;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	int n; cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++){
		cin>>arr[i];
	}
	
	for(int i = 1; i < n; i++){
		if(arr[i]<arr[i-1]){
			pq.push({arr[i],1});
			pq.push({arr[i-1]+1,-1});
			
		}
		else{
			pq.push({arr[i]+1,-1});
			pq.push({arr[i-1],1});
		}
		if(i!=1&& arr[i-2]<arr[i-1]){
			pq.push({arr[i-1],-1});
		}
	}
	
	int ans = 0;
	while(!pq.empty()){
		int a= pq.top().first;
		int x = ans;
		while(!pq.empty()&&pq.top().first==a){
			x+=pq.top().second;
			pq.pop();
		}
		ans = max(x,ans);
	}
	cout<<ans;
	
	return 0;
}