Submission

Score: 100

User: Shangbin

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

Language: cpp

Time: 0.029 second

Submitted On: 2026-03-09 23:05:03

//Problem = https://grader.gchan.moe/problemset/c2_st66_intersection/statement
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e5 + 5, inf = INT_MAX;
int n, p[maxn], a[maxn], b[maxn], line[4 * maxn];
vector<int> ab;

int main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n;
    cin >> p[0];
    ab.push_back(p[0]);
    for (int i = 1; i < n; i++){
        cin >> p[i];
        ab.push_back(p[i]);
        a[i] = min(p[i], p[i - 1]);
        b[i] = max(p[i], p[i - 1]);
    }
    //Path compression
    sort(ab.begin(), ab.end());
    for (int i = 0; i < n; i++){
        a[i] = lower_bound(ab.begin(), ab.end(), a[i]) - ab.begin();
        b[i] = lower_bound(ab.begin(), ab.end(), b[i]) - ab.begin();
        line[a[i]] += 1;
        line[b[i]] -= 1;
    }
    int cur = 0, max_intersect = -inf;
    for (int i = 0; i < (4 * maxn); i++){
        cur += line[i];
        max_intersect = max(max_intersect, cur);
    }
    cout << max_intersect << '\n';
}