记录编号	606656	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	对立猫猫对立	是否通过	通过
代码语言	C++	运行时间	2.549 s
提交时间	2025-10-01 16:45:44	内存使用	25.97 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
struct Node
{
	int x, y;
	int id;
}a[2 * N];
int n, m;
int T = 20;
int ans[N];
int f[2 * N][25];
bool cmp(const Node &a, const Node &b)
{
	return a.x < b.x || a.x == b.x && a.y < b.y;
}
int query(int i, int k)
{
	int t = i;
	for(int j = T; j >= 0; --j)
		if((k >> j) & 1) t = f[t][j];
	return a[t].y - a[i].x;
}
int main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		if(x >= y) y += m;
		a[i] = {x, y, i};
	}
	sort(a + 1, a + n + 1, cmp);
	for(int i = 1; i <= n; i++) a[i + n] = {a[i].x + m, a[i].y + m, a[i].id};
	for(int i = 1; i <= 2 * n; i++) {
		int l = i, r = 2 * n;
		while(l < r) {
			int k = (l + r + 1) / 2;
			if(a[k].x <= a[i].y && a[k].y >= a[i].y) l = k;
			else r = k - 1;
		}
		f[i][0] = l;
	}
	for(int j = 1; j <= T; j++)
		for(int i = 1; i <= 2 * n; i++)
			f[i][j] = f[f[i][j - 1]][j - 1];
	for(int i = 1; i <= n; i++) {
		int l = 0, r = n - 1;
		while(l < r) {
			int k = (l + r) / 2;
			if(query(i, k) >= m) r = k;
			else l = k + 1;
		}
		ans[a[i].id] = l + 1;
	}
	for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	cout << endl;
	return 0;
}