oj.uz

답안 #256961

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
256961 2020-08-03T13:12:10 Z rama_pang Spiral (BOI16_spiral) C++14
29 / 100
 1500 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint MOD = 1e9 + 7;

lint Power(lint x, lint y) {
  if (y == 0) return 1;
  lint res = Power(x, y / 2);
  res = res * res % MOD;
  if (y & 1) res = res * x % MOD;
  return res;
}

lint Inverse(lint x) {
  return Power(x, MOD - 2);
}

using Poly = vector<lint>;

Poly operator + (const Poly &a, const Poly &b) {
  Poly c(max(a.size(), b.size()), 0);
  for (int i = 0; i < (int) a.size(); i++) {
    c[i] += a[i];
  }
  for (int i = 0; i < (int) b.size(); i++) {
    c[i] += b[i];
  }
  for (int i = 0; i < (int) c.size(); i++) {
    c[i] %= MOD;
  }
  return c;
}

Poly operator - (const Poly &a, const Poly &b) {
  Poly c(max(a.size(), b.size()), 0);
  for (int i = 0; i < (int) a.size(); i++) {
    c[i] += a[i];
  }
  for (int i = 0; i < (int) b.size(); i++) {
    c[i] -= b[i];
  }
  for (int i = 0; i < (int) c.size(); i++) {
    c[i] %= MOD;
  }
  return c;
}

Poly operator * (const Poly &a, const Poly &b) {
  Poly c((int) a.size() + b.size() - 1, 0);
  for (int i = 0; i < (int) a.size(); i++) {
    for (int j = 0; j < (int) b.size(); j++) {
      c[i + j] += a[i] * b[j] % MOD;
    }
  }
  for (int i = 0; i < (int) c.size(); i++) {
    c[i] %= MOD;
  }
  return c;
}

Poly operator * (const Poly &a, const lint &b) {
  Poly res = a;
  for (auto &i : res) {
    i *= b;
    i %= MOD;
  }
  return res;
}

Poly Interpolate(const vector<lint> &X, const vector<lint> &Y) {
  Poly res;
  for (int i = 0; i < (int) X.size(); i++) {
    Poly prod = {1};
    lint divis = 1;
    for (int j = 0; j < (int) X.size(); j++) if (i != j) {
      divis = divis * (X[i] - X[j]) % MOD;
      Poly cur = {MOD - X[j], 1};
      prod = prod * cur;
    }
    res = res + prod * (Inverse(divis) * Y[i] % MOD);
  }
  return res;
}

lint Evaluate(const Poly &p, const lint &x) {
  lint cur = 1, res = 0;
  for (int i = 0; i < (int) p.size(); i++) {
    res += p[i] * cur % MOD;
    cur = cur * x % MOD;
  }
  res %= MOD;
  return res;
}

lint Sum(lint L, lint R) {
  return (R - L + 1) * (L + R) / 2 % MOD;
}

lint Line(lint AL, lint AR, lint BL, lint BR, lint val) {
  lint L = max(AL, BL);
  lint R = min(AR, BR);
  if (L <= R) {
    return (Sum(L - AL + 1, R - AL + 1) + ((R - L + 1) * val % MOD)) % MOD;
  }
  return 0;
}

lint Layer(lint L, lint X1, lint Y1, lint X2, lint Y2) {
  if (L == 0) return (X1 <= 0 && 0 <= X2 && Y1 <= 0 && 0 <= Y2);  
  lint res = 0;
  lint val = 1ll * (2 * L + 1) * (2 * L + 1) % MOD;
  val -= 2 * L;
  if (Y1 <= -L && -L <= Y2) {
    res += Line(-L + 1, L, X1, X2, val);
  }
  val -= 2 * L;
  if (X1 <= -L && -L <= X2) {
    res += Line(-L + 1, L, -Y2, -Y1, val);
  }
  val -= 2 * L;
  if (Y1 <= L && L <= Y2) {
    res += Line(-L + 1, L, -X2, -X1, val);
  }
  val -= 2 * L;
  if (X1 <= L && L <= X2) {
    res += Line(-L + 1, L, Y1, Y2, val);
  }
  return res;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  lint N, Q;
  cin >> N >> Q;
  while (Q--) {
    vector<lint> x(4);
    for (int i = 0; i < 4; i++) {
      cin >> x[i];
    }
    {
      lint ans = 0;
      for (int i = 0; i <= N; i++) {
        ans += Layer(i, x[0], x[1], x[2], x[3]);
      }
      ans %= MOD;
      ans = (ans + MOD) % MOD;
      cout << ans << "\n";
      continue;
    }
    vector<lint> events = {0};
    for (int i = 0; i < 4; i++) {
      for (int j = -1; j <= 1; j++) {
        events.emplace_back(abs(x[i]) + j);
      }
    }
    sort(begin(events), end(events));
    events.resize(unique(begin(events), end(events)) - begin(events));
    lint ans = 0;
    for (int i = 0; i + 1 < (int) events.size(); i++) {
      if (events[i] < 0) continue;
      int k = events[i + 1] - events[i];
      if (k >= 4) {
        vector<lint> X(4), Y(4);
        for (int j = 0; j < 4; j++) {
          X[j] = j;
          Y[j] = Layer(events[i] + j, x[0], x[1], x[2], x[3]);
        }
        Poly p = Interpolate(X, Y);
        ans += Evaluate(p, k);
      } else {
        for (int j = events[i]; j < events[i + 1]; j++) {
          ans += Layer(j, x[0], x[1], x[2], x[3]);
        }
      }
    }
    ans %= MOD;
    ans = (ans + MOD) % MOD;
    cout << ans << "\n"; 
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1575 ms 384 KB Time limit exceeded

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 150 ms 384 KB Output is correct

Subtask #4
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1588 ms 384 KB Time limit exceeded

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Execution timed out 1575 ms 384 KB Time limit exceeded