고급반 1주차 풀이 - 반가워요

1. [2228] 구간 나누기 (Gold IV)

너무 당연하게도 DP 문제입니다.

\( DP_{i,j} := \) 첫 \( i \)개의 수에서 \( j \)개의 구간으로 만들 수 있는 최댓값 이라고 정의해봅시다.

 

\( DP_{i,j} \)의 점화식은 아래 2가지 경우로 나눠서 구할 수 있습니다.

A. \( A_{i} \)를 구간에 포함시키지 않기

이 경우, \( i-1 \)개의 수에서 \( j \)개의 구간을 사용하므로 답은 \( DP_{i-1, j} \)가 됩니다.

B. \( A_{k~i} \) 구간을 선택하기

이 경우, \( [1, k-1) \) 구간에서 \( j-1 \)개의 구간을 더 사용해야 하므로 \( DP_{k-2, j-1} + \sum_{l=k}^{i} A_{l} \)가 답이 됩니다.

 

초항은 \( j = 0 \)일 때 \( DP_{i,j} = 0 \)이고, \( i = 0 \text{ and } j \neq 0 \)일 때 \( DP_{i,j} = -\infty \)입니다.

 

시간복잡도는 \( O(N^{2}M) \)입니다.

const ll INF = 1e15;

ll arr[120], prf[120];
ll dp[120][60]; bool chk[120][60];

ll dpf(int n, int m){
	if (m == 0){ return dp[n][m] = 0; }
	if (n <= 0){ return -INF; }
	if (chk[n][m]){ return dp[n][m]; } chk[n][m] = 1;
	ll &res = dp[n][m]; res = -INF; res = max(res, dpf(n-1, m));
	for (int i = 1; i <= n; i++){
		ll val = dpf(i-2, m-1); //cout << n << ' ' << m << " -> " << i-2 << ' ' << m-1 << " = " << res << endl;
		if (val == -INF){ continue; }
		res = max(res, val + prf[n]-prf[i-1]);
	}
	//cout << "DP " << n << ' ' << m << " = " << dp[n][m] << endl;
	return res;
}

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ prf[i] = prf[i-1] + arr[i]; }
	ll ans = -INF;
	for (int i = 1; i <= n; i++){ ans = max(ans, dpf(i, m)); }
	cout << ans;
}

2. [11049] 행렬 곱셈 순서 (Gold III)

역시 DP 문제입니다.

\( DP_{st,ed} := \) \( [st, ed] \) 구간의 행렬을 합치는 데의 최소비용 이라고 정의해봅시다.

 

\( [st, ed] \) 구간의 행렬을 합치려면, \( st \le k \lt ed \)인 \( k \)에 대해 \( [st, k] \)를 합친 뒤, \( (k, ed] \)를 합치고, 최종적으로 \( [st, k] \)와 \( (k, ed] \)를 합쳐주면 됩니다.

이 때의 비용은 \( DP_{st, k} + DP_{k+1, ed} + NMK \)가 되며, 이 때 \( N = A_{st} \)의 세로, \( M = A_{k} \)의 세로, \( K = A_{ed} \)의 세로 입니다.

 

초항은 \( DP_{i,i} = 0 \)이고, 문제의 답은 \( DP_{1, N} \)입니다.

 

시간복잡도는 \( O(N^{3}) \)입니다.

const ll INF = 1e15;
pl2 arr[520];
ll dp[520][520];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	for (int l = 2; l <= n; l++){
		for (int st = 1; ; st++){
			int ed = st + l-1;
			if (ed > n){ break; }
			dp[st][ed] = INF;
			for (int mid = st; mid < ed; mid++){
				dp[st][ed] = min(dp[st][ed], dp[st][mid] + dp[mid+1][ed] + arr[st].fr*arr[mid].sc*arr[ed].sc);
			}
		}
	}
	cout << dp[1][n];
}

3. [1648] 격자판 채우기 (Platinum III)

이번에는 Bit DP입니다.

\( DP_{y, x, bit} := \) 현재 \( (y, x) \)을 보고 있고, 최근 \( M \)칸을 \( bit \)인 상태로 채웠을 때, 남은 칸들을 채우는 경우의 수 라고 정의합시다.

 

이제, 경우를 나눠서 점화식을 구해봅시다.

\( bit \)의 맨 앞 비트 (\( M \)칸 전 = 1칸 위)가 \( 0 \)이라면, 반드시 세로로 채워줘야 합니다.

이 경우의 점화식은 \( DP_{y, x, bit} = DP_{y, x+1, bit<<1|1} \)입니다.

그렇지 않다면, (\( bit \)의 맨 뒤 비트가 꺼져 있다면) 가로로 채우거나 채우지 않고 지나갈 수 있습니다.

이 경우의 점화식은 \( DP_{y, x, bit} = DP_{y, x+1, bit<<1|3} + DP_{y, x+1, bit<<1} \)입니다.

 

초항은 \( DP_{N+1, 1, bit} = 1 \text{ if } bit = 2^{M}-1 \text{ else } 0 \)이고, 답은 \( DP_{1, 1, 2^{M}-1} \)입니다.

 

시간복잡도는 커팅을 동반한 \( O(NM2^{M}) \)입니다.

const int mod = 9901;
int n, m;
int dp[15][15][16390];
int ful;

int dpf(int y, int x, int bit){ bit &= ful;
	//cout << "DPF " << y << ' ' << x << ' ' << bit << endl;
	if (x > m){ x = 1; y += 1; }
	if (y > n){
		//cout << "DP " << y << ' ' << x << ' ' << bitset<6>(bit) << " = " << (bit==ful) << endl;
		if (bit != ful){ return 0; }
		else{ return 1; }
	}
	if (dp[y][x][bit] != -1){ return dp[y][x][bit]; }
	if (~bit & 1<<(m-1)){ dp[y][x][bit] = dpf(y, x+1, bit<<1|1); }
	else{
		dp[y][x][bit] = dpf(y, x+1, bit<<1);
		if (x != 1 && ~bit & 1){ dp[y][x][bit] += dpf(y, x+1, bit<<1|3); }
		dp[y][x][bit] %= mod;
	}
	//cout << "DP " << y << ' ' << x << ' ' << bitset<6>(bit) << " = " << dp[y][x][bit] << endl;
	return dp[y][x][bit];
}

void Main(){
	memset(dp, -1, sizeof(dp));
	cin >> n >> m;
	ful = (1<<m) - 1;
	cout << dpf(1, 1, ful);
}

4. [20506] Kaisar - 생존 (Platinum V)

어떤 정점 \( v \)가 LCA라는 건, 다음 두 가지 경우 중 하나가 됩니다.

1. \( v \)와 \( v \)의 서브트리 속 정점
2. \( v \)의 자식의 서브트리에 속한 두 정점 \( u, w \) (단, \( u, w \)는 다른 서브트리에 속해 있어야 함)

1번 경우는 \( v \)의 서브트리의 크기로 구할 수 있고,

2번 경우는 \( v \)의 자식의 서브트리의 크기들을 사용해 간단히 계산할 수 있습니다.

 

홀수와 짝수를 나눠야 하니, 현재 보고 있는 정점이 홀수/짝수 번째 LCA인지를 추가적으로 저장하면서 구해주면 됩니다.

 

시간복잡도는 \( O(V+E) \)입니다.

vector<int> adj[200020]; vector<ll> arr[200020];
int par[200020]; ll cnt[200020];
bool flg = 1;

void dfs(int now, int par){
	cnt[now] = 1;
	for (int nxt : adj[now]){
		if (nxt == par){ continue; }
		dfs(nxt, now);
		arr[now].push_back(cnt[nxt]);
		cnt[now] += cnt[nxt];
	}
}

void Main(){
	int n; cin >> n;
	int r = 0;
	for (int i = 1; i <= n; i++){
		cin >> par[i];
		if (par[i] == 0){ r = i; }
		else{ adj[ par[i] ].push_back(i); }
	}
	dfs(r, -1);
	ll ans1 = 0, ans2 = 0;
	for (int i = 1; i <= n; i++){
		ll res = 2*cnt[i]-1, sum = cnt[i]-1;
		for (ll c : arr[i]){ res += c * (sum-c); }
		//cout << i << ' ' << res << endl;
		ans1 += res/2 * i; ans2 += res/2 * i;
		if (res & 1){
			if (flg){ ans1 += i; } else{ ans2 += i; }
			flg = !flg;
		}
	}
	cout << ans2 << ' ' << ans1 << endl;
}

5. [10775] 공항 (Gold II)

가능한 공항 중 번호가 가장 큰 걸 고르면 됩니다.

시간복잡도는 \( O(N \alpha (N)) \)입니다.

const int N = 100000;
int par[100020];

int fnd(int a){
	if (par[a] == a){ return a; }
	return par[a] = fnd(par[a]);
}

void Main(){
	for (int i = 1; i <= N; i++){ par[i] = i; }
	int _, n; cin >> _ >> n;
	for (int ans = 0; ans < n; ans++){
		int x; cin >> x;
		int pos = fnd(x);
		if (pos == 0){ cout << ans; return; }
		par[pos] = pos-1;
	}
	cout << n;
}

6. [1700] 멀티탭 스케줄링 (Gold I)

만약 빈 칸이 있으면, 빈 칸에 꽂아주면 됩니다.

이미 꽂혀있다면, 그냥 그대로 쓰면 됩니다.

그럼 안 꽂혀있고, 콘센트를 빼야 한다면?

현재 꽂혀있는 콘센트들 중 '가장 늦게 재사용하는' 콘센트를 빼주면 됩니다. [TODO: 자세한 증명]

 

시간복잡도는 \( O(NM^{2}) \)입니다.

const int INF = 1e9;
vector<int> v;
int arr[120];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= m; i++){ cin >> arr[i]; }
	int ans = 0;
	for (int i = 1; i <= m; i++){
		//cout << "V "; for (int x : v){ cout << x << ' '; } cout << endl;
		bool chk = 0;
		for (int x : v){ chk |= x==arr[i]; }
		if (chk){ continue; }
		if (v.size() < n){ v.push_back(arr[i]); continue; }
		int mx = 0, mxp = 0;
		for (int vi = 0; vi < n; vi++){
			int x = v[vi], pos = INF;
			for (int j = i+1; j <= m; j++){
				if (x == arr[j]){ pos = j; break; }
			}
			if (mx < pos){ mx = pos; mxp = vi; }
		}
		v[mxp] = arr[i]; ans += 1;
	}
	cout << ans;
}

7. [20041] Escaping (Platinum V)

도둑의 최적 전략은 '한 방향으로만 달린다'입니다. [TODO: 자세한 증명]

그렇지 않으면, 경찰이 도둑을 더 잡기 쉽게 만드는 전략이 존재합니다.

 

그럼 경찰이 도둑을 잡을 수 있으려면, 도둑이 달릴 수 있는 4방향 모두에 대해

'그 방향에 경찰을 먼저 놓아서 잡을 수 있는가'를 계산해주면 됩니다. [TODO: 더 자세한 증명]

 

시간복잡도는 \( O(N) \)입니다.

pl2 arr[500020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	pl2 pos; cin >> pos.fr >> pos.sc;
	bool d1=0, d2=0;
	for (int i = 1; i <= n; i++){
		ll dis = abs(arr[i].fr - pos.fr);
		ll dst = abs(arr[i].sc - pos.sc);
		if (dis <= dst){
			if (arr[i].sc < pos.sc){ d1 = 1; }
			else{ d2 = 1; }
		}
	}
	if (!d1 || !d2){ cout << "YES"; return; }
	d1 = d2 = 0;
	for (int i = 1; i <= n; i++){
		ll dis = abs(arr[i].sc - pos.sc);
		ll dst = abs(arr[i].fr - pos.fr);
		if (dis <= dst){
			if (arr[i].fr < pos.fr){ d1 = 1; }
			else{ d2 = 1; }
		}
	}
	if (!d1 || !d2){ cout << "YES"; return; }
	else{ cout << "NO"; }
}

8. [16120] PPAP (Gold IV)

스택에 글자를 하나하나 넣다가 PPAP가 나올 때마다 P로 바꿔주면 됩니다.

최종적으로 P 하나만 남는다면 PPAP, 아니면 NP를 출력하면 됩니다.

[TODO: 자세한 증명]

 

시간복잡도는 \( O(N) \)입니다.

char stk[1000020]; int ptr = 0;

void psh(char ch){ stk[ptr] = ch; ptr += 1; }
void pop(){ ptr -= 1; }

void Main(){
	string s; cin >> s;
	for (char ch : s){
		psh(ch);
		while (ptr >= 4){
			if (stk[ptr-4] == 'P' && stk[ptr-3] == 'P' && stk[ptr-2] == 'A' && stk[ptr-1] == 'P'){ pop(); pop(); pop(); }
			else{ break; }
		}
	}
	if (ptr == 1 && stk[0] == 'P'){ cout << "PPAP"; }
	else{ cout << "NP"; }
}

9. [1655] 가운데를 말해요 (Gold II)

우선순위 큐 2개를 들고 옵시다.

pq1은 중간값 이하의 값들을, pq2는 중간값 초과의 값들을 저장하도록 놓으면,

pq1와 pq2의 원소 개수를 잘 맞춰가는 방식으로 중간값을 pq1의 맨 위에 오도록 조정할 수 있습니다.

시간복잡도는 \( O(N \log N) \)입니다.

priority_queue<int> pq1;
priority_queue< int, vector<int>, greater<int> > pq2;

void Main(){
	int n; cin >> n;
	int l1 = 0, l2 = 0;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		if (i == 1){ pq1.push(x); l1 += 1; }
		else{
			if (x <= pq1.top()){ pq1.push(x); l1 += 1; }
			else{ pq2.push(x); l2 += 1; }
		}
		//l1 < l2 / l1 == l2 or l1 == l2+1 / l1 > l2+1
		while (l1 > l2+1){ pq2.push( pq1.top() ); pq1.pop(); l1 -= 1; l2 += 1; }
		while (l1 < l2){ pq1.push( pq2.top() ); pq2.pop(); l2 -= 1; l1 += 1; }
		cout << pq1.top() << endl;
	}
}

10. [9370] 미확인 도착지 (Gold II)

예술가들의 경로는 \( s \Rightarrow g \rightarrow h \Rightarrow e \) 또는 \( s \Rightarrow h \rightarrow g \Rightarrow e \)로 나타낼 수 있습니다.

그러니 \( s \Rightarrow g \rightarrow h \Rightarrow e \) 또는 \( s \Rightarrow h \rightarrow g \Rightarrow e \)의 길이가 \( s \Rightarrow e \)와 같은 정점들이 있는지 보면 됩니다.

 

\( s, g, h \)에서 다른 모든 정점으로 가는 경로를 미리 계산해주면, \( O(V \log E) \)에 문제를 해결할 수 있습니다.

const ll INF = 1e15;
int n, m, k;
vector<pl2> adj[2020];
ll dis[3][2020];

void f(int st, int idx){
	for (int i = 1; i <= n; i++){ dis[idx][i] = INF; }
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({dis[idx][nxt], nxt});
		}
	}
}

void Main(){
	int t; cin >> t;
	while (t--){
		cin >> n >> m >> k;
		int st, x, y; cin >> st >> x >> y;
		ll d = 0;
		while (m--){
			int a, b, c; cin >> a >> b >> c;
			if (a==x && b==y || a==y && b==x){ d = c; }
			adj[a].push_back({b, c}); adj[b].push_back({a, c});
		}
		f(st, 0); f(x, 1); f(y, 2);
		vector<int> ans;
		while (k--){
			int a; cin >> a;
			//cout << "A  " << a << endl;
			//cout << "D1 " << dis[0][a] << endl;
			//cout << "D2 " << dis[0][x] + d + dis[2][a] << endl;
			//cout << "D3 " << dis[0][y] + d + dis[1][a] << endl;
			if (dis[0][a] == dis[0][x] + d + dis[2][a] || dis[0][a] == dis[0][y] + d + dis[1][a]){ ans.push_back(a); }
		}
		sort( all(ans) );
		for (int x : ans){ cout << x << ' '; }
		cout << endl;
		for (int i = 1; i <= n; i++){ adj[i].clear(); }
	}
}

11. [5719] 거의 최단 경로 (Platinum V)

\( s \)에서 \( v \)로 가는 경로의 길이를 \( d1_{v} \)라고 하고,

\( v \)에서 \( e \)로 가는 경로의 길이를 \( d2_{v} \)라고 하면,

간선 \( v \rightarrow w \)가 최단 경로에 포함된다는 건 \( d1_{v} + E_{v \rightarrow w} + d2_{w} = d1_{e} \)라는 것과 같습니다.

그러니 \( d1 \)과 \( d2 \)를 미리 구한 뒤, 위 조건을 추가해서 다익스트라를 한 번 더 돌려주면 됩니다.

 

시간복잡도는 \( O(V \log E) \)입니다.

const ll INF = 1e15;
int n, m;
vector<pl2> adj[2][520];
ll dis[2][520], res[520];

void f(int st, int idx){
	for (int i = 0; i < n; i++){ dis[idx][i] = INF; }
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
	pq.push({0, st}); dis[idx][st] = 0;
	while (!pq.empty()){
		ll dst = pq.top().fr; int now = pq.top().sc;
		pq.pop();
		if (dst != dis[idx][now]){ continue; }
		for (pl2 p : adj[idx][now]){
			int nxt = p.fr; ll d = p.sc;
			if (dis[idx][nxt] <= d+dst){ continue; }
			dis[idx][nxt] = d+dst;
			pq.push({dis[idx][nxt], nxt});
		}
	}
}

void Main(){
	while (1){
		cin >> n >> m;
		if (n == 0 && m == 0){ return; }
		int st, ed; cin >> st >> ed;
		while (m--){
			int a, b, c; cin >> a >> b >> c;
			adj[0][a].push_back({b, c}); adj[1][b].push_back({a, c});
		}
		f(st, 0); f(ed, 1);
		for (int i = 0; i < n; i++){ res[i] = INF; }
		priority_queue< pl2, vector<pl2>, greater<pl2> > pq;
		pq.push({0, st}); res[st] = 0;
		while (!pq.empty()){
			ll dst = pq.top().fr; int now = pq.top().sc;
			pq.pop();
			if (dst != res[now]){ continue; }
			for (pl2 p : adj[0][now]){
				int nxt = p.fr; ll d = p.sc;
				if (dis[0][now] + d + dis[1][nxt] == dis[0][ed]){ continue; }
				if (res[nxt] <= d+dst){ continue; }
				res[nxt] = d+dst;
				pq.push({res[nxt], nxt});
			}
		}
		if (res[ed] == INF){ cout << -1; } else{ cout << res[ed]; }
		cout << endl;
		for (int i = 0; i < n; i++){ adj[0][i].clear(); adj[1][i].clear(); }
	}
}

12. [15823] 카드 팩 구매하기 (Gold II)

카드 팩의 길이를 \( L \)이라고 고정하면, 슬라이딩 윈도우를 사용하여 구성할 수 있는 카드 팩의 개수를 \( O(N) \)의 시간에 구할 수 있습니다.

\( L \)이 길어지면 카드 팩의 개수 \( m \)이 비증가하므로, \( m \ge M \)인 최대의 \( L \)을 이진 탐색 (파라메트릭 서치)로 찾아주면 됩니다.

 

시간복잡도는 \( O(N \log N) \)입니다.

int arr[100020];
int cnt[500020];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int st = 1, ed = n, ans = 1;
	while (st <= ed){
		int mid = st+ed >> 1;
		int res = 0, num = 0;
		int p1 = 1, p2 = mid;
		for (int i = 1; i <= mid; i++){
			if (cnt[ arr[i] ] == 1){ num -= 1; }
			cnt[ arr[i] ] += 1;
			if (cnt[ arr[i] ] == 1){ num += 1; }
		}
		while (p2 <= n){
			//cout << "P " << p1 << ' ' << p2 << " -> " << num << endl;
			if (num == mid){
				for (int i = p1; i <= p2; i++){ cnt[ arr[i] ] -= 1; }
				num = 0; res += 1;
				p1 = p2+1; p2 = p2+mid;
				if (p2 > n){ break; }
				for (int i = p1; i <= p2; i++){
					if (cnt[ arr[i] ] == 1){ num -= 1; }
					cnt[ arr[i] ] += 1;
					if (cnt[ arr[i] ] == 1){ num += 1; }
				}
			}
			else{
				if (cnt[ arr[p1] ] == 1){ num -= 1; }
				cnt[ arr[p1] ] -= 1;
				if (cnt[ arr[p1] ] == 1){ num += 1; }
				p1 += 1; p2 += 1;
				if (cnt[ arr[p2] ] == 1){ num -= 1; }
				cnt[ arr[p2] ] += 1;
				if (cnt[ arr[p2] ] == 1){ num += 1; }
			}
		}
		//cout << "MID " << mid << ' ' << res << endl;
		if (res >= m){ st = mid+1; ans = mid; } else{ ed = mid-1; }
		memset(cnt, 0, sizeof(cnt));
	}
	cout << ans;
}

13. [19550] 빛의 전사 크리퓨어 (Diamond V)

원형이니, 일단 선형으로 바꿔봅시다. 바꾸는 김에, 포함 관계로 있는 두 구간이 없도록 만들어봅시다.

원형 → 선형은 [st, ed] [st+L, ed+L] 또는 [ed, st+L] 중 더 짧은 걸로 고르면 되고,

포함 관계의 두 직선은 둘 중 더 짧은 것만 남기면 됩니다.

 

이제, 남은 직선들을 st를 기준으로 정렬한 뒤, Sparse하게 답을 구하면 됩니다.

 

\( SPR_{i, j} := i \)번 구간부터 제거를 시작할 때, \( 2^{j} \)회의 제거 연산 후 {남는 구간 중 맨 앞에 있는 구간의 번호와, 이 때 시작 부분을 지난 횟수} 를 정의해봅시다.

그럼 \( SPR_{i, 0} \)은 \( SEG_{i} \)의 끝점에 빔을 날렸을 때의 상태가 되고, \( SPR_{i, j} \)는 \( SPR_{i, j-1} \)과 \( SPR_{SPR_{i,j-1,\text{pos}}, j-1} \)의 조합으로 계산할 수 있습니다.

 

+ 어떤 직선을 제거할 때는 직선의 st에 빔을 날리는 게 최적입니다.

그런데 여기서 제거되지 않는 직선을 찾을 때 ed+1을 기준으로 이진 탐색을 할 수 있습니다.

만약 직선들이 아무렇게나 주어진다면 포함 관계 때문에 ed+1보다 더 작은 위치에 있어도 제거가 안 될 수 있지만, 아까 위에서 포함 관계의 직선들을 다 없애줬기 때문에 st를 기준으로 정렬할 때 ed를 기준으로도 정렬이 되므로 ed+1를 기준으로 찾아줄 수 있습니다.

 

최종 답은 \( i \)번 직선에서부터 시작해서 1바퀴를 돌리기 위해 필요한 제거 연산의 수를 아까 sparse하게 구한 값을 사용해서 \( 2^{20} \)회부터 시뮬레이션을 돌려가면서 찾아주면 됩니다.

 

시간 복잡도는 \( O(N \log N) \)입니다.

[TODO: 설명 수정]

const int N = 20;
pi2 spr[200020][22];
set<pl2> chk;
vector<pl2> v;

void Main(){
	int n, l; cin >> n >> l;
	for (int i = 1; i <= n; i++){
		ll st, ed; cin >> st >> ed;
		if (st > ed){ swap(st, ed); }
		ll cnt = ed-st;
		if (cnt*2 >= l){
			v.push_back({ed, st+l});
			//cout << "V " << ed << ' ' << st+l << endl;
		}
		else{
			v.push_back({st, ed}); v.push_back({st+l, ed+l});
			//cout << "V " << st << ' ' << ed << endl;
			//cout << "V " << st+l << ' ' << ed+l << endl;
		}
	}
	sort(all(v), [](pl2 a, pl2 b){
		if (a.fr != b.fr){ return a.fr > b.fr; }
		return a.sc < b.sc;
	});
	vector<pl2> pos;
	ll mn = 1e15; int m = 0;
	for (pl2 p : v){
		if (p.sc >= mn){ continue; }
		mn = min(mn, p.sc);
		if (p.fr < l && p.sc >= l){
			pos.push_back(p); m += 1;
			pos.push_back({p.fr+l, p.sc+l});
		}
		else if (p.fr >= l && p.sc >= l){ chk.insert(p); }
		else{
			if (chk.find({p.fr+l, p.sc+l}) != chk.end()){
				pos.push_back(p); m += 1;
				pos.push_back({p.fr+l, p.sc+l});
			}
		}
	}
	sort(all(pos));
	//for (pl2 p : pos){ cout << "P " << p.fr << ' ' << p.sc << endl; }
	for (int i = 0; i < m; i++){
		pl2 tar = {pos[i].sc+1, 0};
		auto it = lower_bound(all(pos), tar);
		int res = it - pos.begin();
		if (res < m){ spr[i][0] = {res, 0}; }
		else{
			pl2 p = *it; tar = {p.fr-l, p.sc-l};
			it = lower_bound(all(pos), tar);
			spr[i][0] = {it - pos.begin(), 1};
		}
		//cout << "SPR " << i << ' ' << 0 << " = " << spr[i][0].fr << ' ' << spr[i][0].sc << endl;
	}
	for (int j = 1; j <= N; j++){
		for (int i = 0; i < m; i++){
			spr[i][j].fr = spr[ spr[i][j-1].fr ][j-1].fr;
			spr[i][j].sc = spr[i][j-1].sc + spr[ spr[i][j-1].fr ][j-1].sc;
			spr[i][j].sc = min(spr[i][j].sc, 2);
			//cout << "SPR " << i << ' ' << j << " = " << spr[i][j].fr << ' ' << spr[i][j].sc << endl;
		}
	}
	int ans = 1e9;
	for (int i = 0; i < m; i++){
		int res = 0; pi2 p = {i, 0};
		for (int j = N; j >= 0; j--){
			if (p.sc + spr[p.fr][j].sc == 0 ||
				p.sc + spr[p.fr][j].sc == 1 && spr[p.fr][j].fr < i){
					res += 1<<j;
					p.sc += spr[p.fr][j].sc;
					p.fr = spr[p.fr][j].fr;
			}
		}
		ans = min(ans, res+1);
	}
	cout << ans;
}