记录编号	606666	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	LikableP	是否通过	通过
代码语言	C++	运行时间	1.840 s
提交时间	2025-10-01 17:07:12	内存使用	22.44 MiB

#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 2e5 + 10;

struct Item {
  int l, r, id;
} a[MAXN << 1];

int n, m;
int f[MAXN << 1][20];
int ans[MAXN];

int main() {
  freopen("flagplan.in", "r", stdin);
  freopen("flagplan.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(false), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].l >> a[i].r;
    if (a[i].l > a[i].r) a[i].r += m;
    a[i].id = i;
  }

  sort(a + 1, a + n + 1, [](Item x, Item y) {
    if (x.l != y.l) return x.l < y.l;
    return x.r < y.r;
  });

  for (int i = 1; i <= n; ++i) {
    a[i + n] = {a[i].l + m, a[i].r + m, a[i].id};
  }

  for (int i = 1; i <= n << 1; ++i) {
    int l = i, r = n << 1, ans;
    while (l <= r) {
      int mid = l + ((r - l) >> 1);
      if (a[mid].l <= a[i].r && a[mid].r >= a[i].r) {
        ans = mid;
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    f[i][0] = ans;
  }

  for (int j = 1; j <= 19; ++j) {
    for (int i = 1; i <= n << 1; ++i) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }

  auto query = [](int i, int k) -> int {
    int t = i;
    for (int i = 19; i >= 0; --i) {
      if (k >> i & 1) t = f[t][i];
    }
    return a[t].r - a[i].l;
  };

  for (int i = 1; i <= n; ++i) {
    int l = 0, r = n - 1, ans;
    while (l <= r) {
      int mid = l + ((r - l) >> 1);
      if (query(i, mid) >= m) {
        ans = mid;
        r = mid - 1;
      } else {
        l = mid + 1;
      }
    }
    ::ans[a[i].id] = ans;
  }

  for (int i = 1; i <= n; ++i) {
    cout << ans[i] + 1 << " ";
  }
  cout << endl;
  return 0;
}