Submission

Score: 100

User: Hxluk.ka

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

Language: cpp

Time: 0.037 second

Submitted On: 2026-01-30 22:34:06

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()
const int nx=1e5+3;
ll n, p[nx], l[nx], r[nx], add[2*nx], rem[2*nx], sm, mx;
vector<ll> srt;
int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin>>n;
    cin>>p[0];
    for (int i=1; i<n; i++) {
        cin>>p[i];
        l[i]=min(p[i], p[i-1]);
        r[i]=max(p[i], p[i-1]);
        srt.pb(l[i]);
        srt.pb(r[i]);
    }
    sort(all(srt));
    srt.erase(unique(all(srt)), srt.end());

    for (int i=1; i<n; i++) {
        l[i]=lower_bound(all(srt), l[i])-srt.begin();
        r[i]=lower_bound(all(srt), r[i])-srt.begin();

        add[l[i]]++;
        rem[r[i]]++;
    }

    for (int i=0; i<srt.size(); i++) {
        sm+=add[i]-rem[i];
        mx=max(mx, sm);
    }
    cout<<mx;
}