Submission

Score: 0

User: KantaponZ

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

Language: cpp

Time: 0.002 second

Submitted On: 2025-09-02 22:25:27

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

#define float double

int N;
double P[100005];
vector<pair<double,double>> a;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> P[i];
    }
    for (int i = 1; i + 1 <= N; i++) {
        if (i == 1) a.emplace_back(min(P[i], P[i + 1]), max(P[i], P[i + 1]));
        if (i != 1) {
            if (P[i + 1] < P[i]) {
                a.emplace_back(min(P[i], P[i + 1]), max(P[i], P[i + 1]) - 0.05);
            } else {
                a.emplace_back(min(P[i], P[i + 1]) + 0.05, max(P[i], P[i + 1]));
            }
        }
    }
    sort(a.begin(), a.end());
    double r = a[N - 2].first;
    int ct = 0;
    int ans = 0;
    queue<double> q;
    for (int i = N - 2; i >= 0; i--) {
        if (a[i].second < r) {
            ans = max(ans, ct);
            r = a[i].first;
            while (!q.empty() && q.front() > a[i].second) ct--, q.pop();
            ct++;
            q.push(r);
            //cout << "(r, c): " << r << " " << ct << "\n" << a[i].first << " " << a[i].second << "\n";
            continue;
        }
        
        q.push(a[i].first);
        ct++;
        //cout << "(r, c): " << r << " " << ct << "\n" << a[i].first << " " << a[i].second << "\n";
    }
    ans = max(ans, ct);
    cout << ans;
}

/*

7                                                             
1 2 1 2 1 3 2
*/