oj.uz

Submission #256995

# Submission time Handle Problem Language Result Execution time Memory
256995 2020-08-03T13:43:22 Z rama_pang Spiral (BOI16_spiral) C++14
100 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const lint MOD = 1e9 + 7;
using Poly = vector<lint>;

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);
}

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;
    if (c[i] < 0) 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;
      c[i + j] %= MOD;
    }
  }
  for (int i = 0; i < (int) c.size(); i++) {
    c[i] %= MOD;
    if (c[i] < 0) c[i] += MOD;
  }
  return c;
}

Poly operator * (const Poly &a, const lint &b) {
  Poly res = a;
  for (auto &i : res) {
    i *= b;
    i %= MOD;
    if (i < 0) 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;
  val %= MOD;
  if (val < 0) val += MOD;
  if (Y1 <= -L && -L <= Y2) {
    res += Line(-L + 1, L, X1, X2, val);
  }
  val -= 2 * L;
  val %= MOD;
  if (val < 0) val += MOD;
  if (X1 <= -L && -L <= X2) {
    res += Line(-L + 1, L, -Y2, -Y1, val);
  }
  val -= 2 * L;
  val %= MOD;
  if (val < 0) val += MOD;
  if (Y1 <= L && L <= Y2) {
    res += Line(-L + 1, L, -X2, -X1, val);
  }
  val -= 2 * L;
  val %= MOD;
  if (val < 0) val += MOD;
  if (X1 <= L && L <= X2) {
    res += Line(-L + 1, L, Y1, Y2, val);
  }
  return res;
}

lint Brute(vector<lint> x) {
  lint ans = 0;
  lint mx = max({abs(x[0]), abs(x[1]), abs(x[2]), abs(x[3])});
  for (int i = 0; i <= mx; i++) {
    ans += Layer(i, x[0], x[1], x[2], x[3]);
  }
  ans %= MOD;
  ans = (ans + MOD) % MOD;
  return ans;
}

lint Solve(vector<lint> x) {
  vector<lint> events = {0, 1, 2};
  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;
    lint k = events[i + 1] - events[i];
    const int DEG = 5;
    if (k >= DEG) {
      vector<lint> X(DEG), Y(DEG);
      for (int j = 0; j < DEG; j++) {
        X[j] = j;
        Y[j] = Layer(events[i] + j, x[0], x[1], x[2], x[3]);
        if (j > 0) {
          Y[j] += Y[j - 1];
          Y[j] %= MOD;
        }
      }
      Poly p = Interpolate(X, Y);
      ans += Evaluate(p, k - 1);
    } 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;
  return ans;
}

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];
    }
    cout << Solve(x) << "\n";
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct