Submission

Score: 100

User: meme_boi2

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

Language: cpp

Time: 0.042 second

Submitted On: 2026-03-20 11:34:50

#include <bits/stdc++.h>
using namespace std;
#define pii pair<double,double>
bool comp(pair<double,int> a, pair<double,int> b){
    if(a.first == b.first){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}
int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<double> pd(n);
    for(auto &x: pd) cin >> x;
    vector<pii> mat(n-1);
    mat[0] = {pd[0],pd[1]};
    
    vector<pair<double,int>> dp;
    if(mat[0].first > mat[0].second){
        swap(mat[0].first,mat[0].second);
    }
    for(int i = 0; i < n - 1; i++){
        if(pd[i] == pd[i+1]) continue; 
        double dd = min(pd[i], pd[i+1]);
        double pp = max(pd[i], pd[i+1]);
        
        dp.push_back({dd, 1});
        dp.push_back({pp, -1});
    }
    sort(dp.begin(),dp.end(),comp);
    int ans = 0, cur = 0;
    for(auto [x,y] : dp){
        cur += y;
        ans = max(ans,cur);
    }
    cout << ans;
}