Submission

Score: 100

User: kittipos

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

Language: cpp

Time: 0.028 second

Submitted On: 2026-03-09 20:08:17

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    int64_t pre = 0;

    priority_queue<int64_t, vector<int64_t>, greater<int64_t>> enter;
    priority_queue<int64_t, vector<int64_t>, greater<int64_t>> drop;
    for (int i = 0; i < n; i++) {
        int64_t temp;
        cin >> temp;
        if (i == 0) {
            pre = temp;
            continue;
        }

        int64_t e = temp;
        int64_t d = pre;
        
        if (e > d) {
            swap(e, d);
        }

        e *= 2;
        d *= 2;
        
        // goes down
        if (i != 0) {
            if (pre > temp) {
                d--;
            } else {
                e++;
            }
        }
        
        
        enter.push(e);
        drop.push(d);
        pre = temp;
    }
    

    int64_t cur = 0;
    int64_t most = 0;
    while (!enter.empty() || !drop.empty()) {
        if (enter.empty()) {
            break;
        }

        if (enter.top() > drop.top()) {
            cur--;
            drop.pop();            
        } else {
            cur++;
            enter.pop();
        }
        most = max(cur, most);
    }

    cout << most;

    return 0;
}