求助三代目,再去重构我把屏幕吃下去
查看原帖
求助三代目,再去重构我把屏幕吃下去
20522
ccviolett楼主2020/5/7 21:17

我已经不行了,代码已经极致简化、对拍过了,还是 WA 两个点。

你谷真是毒瘤,希望能有你谷的大佬救我。

重构是不可能重构的,这样都看不出错误来了,重构我把屏幕吃下去。

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

const int N = 5e5 + 1;
const int M = 1e7 + 1;
const int MOD = 1e9 + 7;

int n;
long long x[N], r[N];
int node_able_l[N], node_able_r[N];
int tree_id[N];

int tree_able_l[M], tree_able_r[M];
int top, fi[M], ne[M], to[M];
int tot, col[M];
int cir_able_l[M], cir_able_r[M], cir_res[M];
int T, dfn[M], low[M];
int cnt, sta[M];
bool insta[M];

long long read();
void Add(int u, int v);
void Build(int t = 1, int l = 1, int r = n);
void Modify(int x, int y, int id, int t = 1, int l = 1, int r = n);
void Tarjan(int t);

signed 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;
  }
  Build();
  for (int i = 1; i <= n; ++i) 
    Modify(node_able_l[i], node_able_r[i], tree_id[i]);

  for (int i = 1; i <= n; ++i) {
    if (!dfn[tree_id[i]]) Tarjan(tree_id[i]);
  }
  for (int i = 1; i <= tot; ++i) 
    cir_res[i] = cir_able_r[i] - cir_able_l[i] + 1;
  long long res = 0;
  for (int i = 1; i <= n; ++i) {
    int able_num = cir_res[col[tree_id[i]]];
    (res += (1ll * i * able_num) % MOD) %= MOD;
  }
  printf("%lld\n", res);
  return 0;
}

long long read() {
  long long 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;
}

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

void Build(int t, int l, int r) {
  int mid = (l + r) >> 1;
  if (l == r) {
    tree_id[mid] = t;
    tree_able_l[t] = node_able_l[mid];
    tree_able_r[t] = node_able_r[mid];
    return ;
  }
  Build(t << 1, l, mid), Build(t << 1 | 1, mid + 1, r);
  Add(t, t << 1), Add(t, t << 1 | 1);
  tree_able_l[t] = tree_able_l[t << 1];
  tree_able_r[t] = tree_able_r[t << 1 | 1];
}

void Modify(int x, int y, int tree_id, int t, int l, int r) {
  if (x <= l && r <= y) {
    if (tree_id != t) Add(tree_id, t);
    return ;
  }
  int mid = (l + r) >> 1;
  if (x <= mid) Modify(x, y, tree_id, t << 1, l, mid);
  if (y > mid) Modify(x, y, tree_id, t << 1 | 1, mid + 1, r);
}

void Tarjan(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]]) {
      Tarjan(to[i]), low[t] = min(low[t], low[to[i]]);
      tree_able_l[t] = min(tree_able_l[t], tree_able_l[to[i]]);
      tree_able_r[t] = max(tree_able_r[t], tree_able_r[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] = tree_able_l[t];
    cir_able_r[tot] = tree_able_r[t];
    while (sta[cnt + 1] != t) {
      int x = sta[cnt--];
      insta[x] = false, col[x] = tot;
    }
  }
}
2020/5/7 21:17
加载中...