无法下载数据,LOJ 通过,72 分求助
查看原帖
无法下载数据,LOJ 通过,72 分求助
20522
ccviolett楼主2020/5/7 19:36

代码尽量按照 Google 代码规范去书写了,可能有点臃肿。

有大佬可以帮忙看看哪里出问题了吗?

typedef long long readtype;

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

typedef long long var;
typedef long double let;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}
/* }}} */

const int N = 4e6 + 1;
const int M = 4e6 + 1;
const int MOD = 1e9 + 7;

struct Line {
  int u, v;
};

int n;
var x[N], r[N];
int node_able_l[N], node_able_r[N];
int m;
Line line[M];
namespace seg_tree_space {
  int T, root, lson[N << 2], rson[N << 2];
  int rnk[N << 2];
  void Build(int &t = root, int l = 1, int r = n);
  void Modify(int x, int y, int id, int t = root, int l = 1, int r = n);
};
int seg_tree_id[N], tree_able_l[N], tree_able_r[N];
int top, fi[N], ne[M << 1], to[M << 1];
void Add(int u, int v);
int tot, col[N], size[N];
int cir_able_l[N], cir_able_r[N];
namespace tarjan_space {
  int T, dfn[N], low[N];
  int cnt, sta[N];
  bool insta[N];
  void GetCir(int t);
};
struct Union {
  int fa[N];
  void Init(int n) {
    for (int i = 1; i <= n; ++i) fa[i] = i;
  }
  int Find(int t) {
    if (fa[t] != t) fa[t] = Find(fa[t]);
    return fa[t];
  }
  bool Merge(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return false;
    fa[x] = y;
    return true;
  }
} uni;
bool mark[N];
void GetCirAble(int t);

int main() {
  n = read();
  for (int i = 1; i <= n; ++i) 
    x[i] = read(), r[i] = read();
  for (int i = 1; i <= n; ++i) {
    node_able_l[i] = lower_bound(x + 1, x + n + 1, x[i] - r[i]) - x;
    node_able_r[i] = upper_bound(x + 1, x + n + 1, x[i] + r[i]) - x - 1;
  }

  seg_tree_space::Build();
  for (int i = 1; i <= n; ++i) 
    seg_tree_space::Modify(node_able_l[i], node_able_r[i], seg_tree_id[i]);

  for (int i = 1; i <= seg_tree_space::T; ++i) {
    if (!tarjan_space::dfn[i]) tarjan_space::GetCir(i);
  }

  uni.Init(tot);

  top = 0;
  memset(fi, 0, sizeof(fi));
  for (int i = 1; i <= m; ++i) {
    int u = col[line[i].u], v = col[line[i].v];
    if (!uni.Merge(u, v)) continue;
    Add(u, v);
  }
  for (int i = 1; i <= tot; ++i) {
    if (!mark[i]) GetCirAble(i);
  }
  var res = 0;
  for (int i = 1; i <= n; ++i) {
    var able_num = cir_able_r[col[seg_tree_id[i]]] - cir_able_l[col[seg_tree_id[i]]] + 1;
    (res += (able_num * i) % MOD) %= MOD;
  }
  printf("%lld\n", res);
  return 0;
}

namespace seg_tree_space {
  void Build(int &t, int l, int r) {
    t = ++T;
    int mid = (l + r) >> 1;
    if (l == r) {
      seg_tree_id[mid] = t;
      tree_able_l[t] = node_able_l[mid];
      tree_able_r[t] = node_able_r[mid];
      return ;
    }
    tree_able_l[t] = n, tree_able_r[t] = 1;
    Build(lson[t], l, mid), Build(rson[t], mid + 1, r);
    Add(t, lson[t]), Add(t, rson[t]);
    line[++m] = (Line) {t, lson[t]}, line[++m] = (Line) {t, rson[t]};
  }
  void Modify(int x, int y, int seg_tree_id, int t, int l, int r) {
    if (x > r || y < l) return ;
    if (x <= l && r <= y) {
      Add(seg_tree_id, t);
      line[++m] = (Line) {seg_tree_id, t};
      return ;
    }
    int mid = (l + r) >> 1;
    Modify(x, y, seg_tree_id, lson[t], l, mid);
    Modify(x, y, seg_tree_id, rson[t], mid + 1, r);
  }
}

void Add(int u, int v) {
  ne[++top] = fi[u], fi[u] = top, to[top] = v;
}

namespace tarjan_space {
  void GetCir(int t) {
    dfn[t] = low[t] = ++T;
    sta[++cnt] = t;
    insta[t] = true;
    for (int i = fi[t]; i; i = ne[i]) {
      if (!dfn[to[i]]) GetCir(to[i]), low[t] = min(low[t], low[to[i]]);
      else if (insta[to[i]]) low[t] = min(low[t], dfn[to[i]]);
    }
    if (dfn[t] == low[t]) {
      tot++;
      cir_able_l[tot] = n, cir_able_r[tot] = 1;
      while (sta[cnt + 1] != t) {
        int x = sta[cnt--];
        insta[x] = false, col[x] = tot;
        cir_able_l[tot] = min(cir_able_l[tot], tree_able_l[x]);
        cir_able_r[tot] = max(cir_able_r[tot], tree_able_r[x]);
      }
    }
  }
};

void GetCirAble(int t) {
  mark[t] = true;
  for (int i = fi[t]; i; i = ne[i]) {
    if (!mark[to[i]]) GetCirAble(to[i]);
    cir_able_l[t] = min(cir_able_l[t], cir_able_l[to[i]]);
    cir_able_r[t] = max(cir_able_r[t], cir_able_r[to[i]]);
  }
}
2020/5/7 19:36
加载中...