Submission

Score: 0

User: august

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

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-18 19:45:21

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

#define int long long

bool cmp(pair<int,int> &a, pair<int,int> &b) {
    if (a.first == b.first) return b.second < a.second;
    return a.first < b.first;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin>> n;

    int a[n];
    for (int i=0; i<n; i++) cin>> a[i];
    
    vector<pair<int,int>> sw;
    int prvmx = -1;
    for (int i=0; i<n-1; i++) {
        int mn = min(a[i], a[i+1]);
        int mx = max(a[i], a[i+1]);

        sw.push_back({mn, 1});
        if (prvmx != mx) {
            sw.push_back({mx, -1});
            sw.push_back({mx, 1});
            prvmx = mx;
        }
        sw.push_back({mx-1, -1});
    }

    sort(sw.begin(), sw.end(), cmp);
    int cnt=0, ans=0;
    for (auto &x : sw) {
        
        cnt+=x.second;
        //cout<< x.first<< ' '<< cnt<< '\n';
        ans = max(ans, cnt);
    }
    cout<< ans;
}