Submission

Score: 100

User: SnowAveNode

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

Language: cpp

Time: 0.026 second

Submitted On: 2026-03-01 11:00:07

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;

    vector<long long> p(n);
    for(int i = 0; i < n; i++) cin >> p[i];

    vector<pair<long long,int>> ev;

    for(int i = 0; i < n-1; i++){
        long long lo = min(p[i], p[i+1]);
        long long hi = max(p[i], p[i+1]);

        ev.push_back({lo, +1});
        ev.push_back({hi, -1});
    }

    sort(ev.begin(), ev.end());

    int ans = 0, cur = 0;

    for(int i = 0; i < (int)ev.size(); ){
        long long y = ev[i].first;

        while(i < (int)ev.size() && ev[i].first == y && ev[i].second == +1){
            cur++;
            i++;
        }

        ans = max(ans, cur);

        while(i < (int)ev.size() && ev[i].first == y && ev[i].second == -1){
            cur--;
            i++;
        }
    }

    cout << ans;
}