Submission

Score: 100

User: Ninstroyer

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

Language: cpp

Time: 0.035 second

Submitted On: 2026-01-17 14:48:10

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

const int nx = 1e5+5;

int n,p[nx],l[nx],r[nx],add[nx],sub[nx];
vector<int> value;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    cin>>p[0];
    for(int i = 1; i < n; i++)
    {
        cin>>p[i];
        int left = p[i-1], right = p[i];
        if(left > right) swap(left,right);
        l[i] = left;
        r[i] = right;
        value.push_back(left), value.push_back(right);
    }
    sort(value.begin(),value.end());
    value.erase(unique(value.begin(),value.end()),value.end());
    for(int i = 1; i < n; i++)
    {
        l[i] = lower_bound(value.begin(),value.end(),l[i])-value.begin();
        r[i] = lower_bound(value.begin(), value.end(), r[i])-value.begin();
        add[l[i]]++;
        sub[r[i]]++;
    }
    int mx = 0, sm = 0;
    for(int i = 0; i < value.size(); i++)
    {
        sm += add[i];
        sm -= sub[i];
        mx = max(mx, sm);
    }
    cout<<mx;
}