Submission

Score: 100

User: singtoppy

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

Language: cpp

Time: 0.023 second

Submitted On: 2026-03-09 16:45:41

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

#define ll long long
#define pii pair<int, int>

//sweep line algorithm

int n, A[100005];

vector<pii> t;

void solve () {
	cin >> n;
	cin >> A[0];
	for(int i = 1; i < n; i++) {
		cin >> A[i];
		int st = min(A[i], A[i - 1]), en = max(A[i], A[i - 1]);
		t.push_back({st, 1});
		t.push_back({en, -1});
	} 
	sort(t.begin(), t.end());
	int cnt = 0, res = 0;
	for(int i = 0; i < t.size(); i++) {
		cnt += t[i].second;
		res = max(res, cnt);
	}
	cout << res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);	

	solve();

	return 0;
}