Submission

Score: 100

User: Zonezonee

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

Language: cpp

Time: 0.022 second

Submitted On: 2026-01-16 19:20:36

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int sweep[N], a[N];
vector<int> t;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    t.resize(n);
    for(int i = 1; i <= n; ++i) cin >> a[i], t[i-1] = a[i];
    sort(t.begin(), t.end());
    t.erase(unique(t.begin(), t.end()), t.end());
    for(int i = 1; i <= n; ++i){
        a[i] = lower_bound(t.begin(), t.end(), a[i])-t.begin() + 1;
    }
    for(int i = 1; i < n; ++i){
        int l = min(a[i], a[i+1]), r = max(a[i], a[i+1]);
        sweep[l]++;
        sweep[r]--;
    }
    int ans = 0;
    for(int i = 1; i <= n; ++i) ans = max(ans, sweep[i] = sweep[i] + sweep[i-1]);
    cout << ans << '\n';
}