Submission

Score: 100

User: Neozaawwman1

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

Language: cpp

Time: 0.027 second

Submitted On: 2026-03-16 19:30:51

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<int,int> a, pair<int,int> b){
    if(a.first!=b.first){
        return a.first<b.first;
    }else{
        return a.second<b.second;
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n;cin>>n;
    vector<int> v;
    for(int i=0; i<n; i++){
        int x;cin>>x;
        v.push_back(x);
    }
    vector<pair<int,int>> ev;
    for(int i=1; i<n; i++){
        int b = max(v[i],v[i-1]);
        int a = min(v[i],v[i-1]);
        ev.push_back({a,+1});
        ev.push_back({b,-1});
    }
    sort(ev.begin(),ev.end(),cmp);
    int ans=-1;
    int cur =0;
    for(int i=0; i<ev.size(); i++){
        cur+=ev[i].second;
        ans = max(ans,cur);
    }
    cout<<ans;
    return 0;
}