Submission #51357

#	Time	Username	Problem	Language	Result	Execution time	Memory
51357		mareksom	Spiral (BOI16_spiral)	C++17	100 / 100	42 ms	536 KiB

spiral

#ifndef LOCAL
#pragma GCC optimize ("O3")
#endif

#include <bits/stdc++.h>

using namespace std;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return {i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (c it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(x...) " [" #x ": " << (x) << "] "

using ld = long double;
using ll = long long;

constexpr int mod = 1000 * 1000 * 1000 + 7;
constexpr int odw2 = (mod + 1) / 2;

void OdejmijOd(int& a, int b) { a -= b; if (a < 0) a += mod; }
int Odejmij(int a, int b) { OdejmijOd(a, b); return a; }
void DodajDo(int& a, int b) { a += b; if (a >= mod) a -= mod; }
int Dodaj(int a, int b) { DodajDo(a, b); return a; }
int Mnoz(int a, int b) { return (ll) a * b % mod; }
void MnozDo(int& a, int b) { a = Mnoz(a, b); }
int Pot(int a, int b) { int res = 1; while (b) { if (b % 2 == 1) MnozDo(res, a); a = Mnoz(a, a); b /= 2; } return res; }
int Odw(int a) { return Pot(a, mod - 2); }
void PodzielDo(int& a, int b) { MnozDo(a, Odw(b)); }
int Podziel(int a, int b) { return Mnoz(a, Odw(b)); }
int Moduluj(ll x) { x %= mod; if (x < 0) x += mod; return x; }

template <typename T> T Maxi(T& a, T b) { return a = max(a, b); }
template <typename T> T Mini(T& a, T b) { return a = min(a, b); }

struct Wiel {
  vector<int> wsp;

  template <typename ...Args>
  Wiel(Args ...args) : wsp{args...} {}

  int Oblicz(int n) const {
    int res = 0;
    for (int i = (int) wsp.size() - 1; i >= 0; i--) {
      MnozDo(res, n);
      DodajDo(res, wsp[i]);
    }
    return res;
  }

  void Kanon() {
    while (!wsp.empty() and wsp.back() == 0) {
      wsp.pop_back();
    }
  }

  Wiel operator*(const Wiel& w) const {
    Wiel res;
    res.wsp.resize(wsp.size() + w.wsp.size() + 2);
    for (int i = 0; i < (int) wsp.size(); i++) {
      for (int j = 0; j < (int) w.wsp.size(); j++) {
        DodajDo(res.wsp[i + j], Mnoz(wsp[i], w.wsp[j]));
      }
    }
    res.Kanon();
    return res;
  }

  Wiel& operator*=(const Wiel& w) {
    return *this = *this * w;
  }

  Wiel& operator+=(const Wiel& w) {
    wsp.resize(max(wsp.size(), w.wsp.size()));
    for (int i = 0; i < (int) w.wsp.size(); i++) {
      DodajDo(wsp[i], w.wsp[i]);
    }
    Kanon();
    return *this;
  }

  Wiel& operator-=(const Wiel& w) {
    wsp.resize(max(wsp.size(), w.wsp.size()));
    for (int i = 0; i < (int) w.wsp.size(); i++) {
      OdejmijOd(wsp[i], w.wsp[i]);
    }
    Kanon();
    return *this;
  }

  Wiel operator+(const Wiel& w) const {
    return Wiel(*this) += w;
  }

  Wiel operator-(const Wiel& w) const {
    return Wiel(*this) -= w;
  }

  Wiel& operator*=(int val) {
    for (int& x : wsp) {
      MnozDo(x, val);
    }
    Kanon();
    return *this;
  }

  Wiel operator*(int val) const {
    return Wiel(*this) *= val;
  }

  Wiel& operator/=(int val) {
    return *this *= Odw(val);
  }

  Wiel operator/(int val) const {
    return Wiel(*this) /= val;
  }

  Wiel PrefiksSum() const {
    Wiel result;
    for (int i = 0; i < (int) wsp.size(); i++) {
      result += SumaPoteg(i) * wsp[i];
    }
    return result;
  }

  static vector<Wiel> suma_poteg;

  static const Wiel& SumaPoteg(int pot) {
    auto ObliczSumePoteg = [](int p) -> Wiel {
      return Interpoluj(
          [p](int n) -> int {
            if (p == 0) return n + 1;
            int suma = 0;
            for (int i = 0; i <= n; i++) {
              DodajDo(suma, Pot(i, p));
            }
            return suma;
          }, p + 2);
    };
    while (pot >= (int) suma_poteg.size()) {
      suma_poteg.push_back(ObliczSumePoteg((int) suma_poteg.size()));
    }
    return suma_poteg[pot];
  }

  template <typename F>
  static Wiel Interpoluj(F f, int n) {
    Wiel wynik;
    for (int i = 0; i < n; i++) {
      Wiel skladnik(1);
      for (int j = 0; j < n; j++) {
        if (i != j) {
          skladnik *= Wiel(Odejmij(0, j), 1) / Odejmij(i, j);
        }
      }
      wynik += skladnik * f(i);
    }
    return wynik;
  }
};

vector<Wiel> Wiel::suma_poteg;

debug& operator<<(debug& deb, const Wiel& w) {
  if (w.wsp.empty()) {
    return deb << "0";
  }
  deb << w.wsp[0];
  for (int i = 1; i < (int) w.wsp.size(); i++) {
    deb << " + " << w.wsp[i] << " * x";
    if (i > 1) {
      deb << "^" << i;
    }
  }
  return deb;
}

int Get(int x, int y) {
  if (x == 0 and y == 0) return 1;
  const int m = max(abs(x), abs(y)) - 1;
  int wart = Mnoz(m * 2 + 1, m * 2 + 1);
  DodajDo(wart, 1);
  int a = m + 1, b = -m;
  if (a == x and b <= y) {
    return Dodaj(wart, Moduluj(y - b));
  }
  const int skok_mod = Moduluj((m + 1) * 2);
  DodajDo(wart, Odejmij(skok_mod, 1));
  b += (m + 1) * 2 - 1;
  if (b == y and x < a) {
    return Dodaj(wart, Moduluj(a - x));
  }
  DodajDo(wart, skok_mod);
  a -= (m + 1) * 2;
  if (a == x and y < b) {
    return Dodaj(wart, Moduluj(b - y));
  }
  DodajDo(wart, skok_mod);
  b -= (m + 1) * 2;
  if (b == y and a < x) {
    return Dodaj(wart, Moduluj(x - a));
  }
  assert(false);
}

// Returns (0^pot + 1^pot + ... + n^pot) % mod.
int SumujPot(int n, int pot) {
  return Wiel::SumaPoteg(pot).Oblicz(n);

  n = Moduluj(n);
  if (pot == 0) {
    return Dodaj(n, 1);
  } else if (pot == 1) {
    //static int odw2 = Odw(2);
    return Mnoz(Mnoz(n, Dodaj(n, 1)), odw2);
  } else if (pot == 2) {
    static int odw6 = Odw(6);
    return Mnoz(Mnoz(n, Dodaj(n, 1)), Mnoz(Dodaj(Dodaj(n, n), 1), odw6));
  } else {
    assert(false);
  }
}

int Gora(int y) {
  assert(y >= 0);
  return Dodaj(Mnoz(4, SumujPot(y, 2)), Odejmij(SumujPot(y, 0), SumujPot(y, 1)));
//  int suma = 0;
//  for (int a = 0; a <= y; a++) {
//    DodajDo(suma, Get(0, a));
//  }
//  return suma;
}

int Dol(int y) {
  assert(y <= 0);
  return Dodaj(Mnoz(4, SumujPot(-y, 2)), Dodaj(Mnoz(3, SumujPot(-y, 1)), SumujPot(-y, 0)));
//  int suma = 0;
//  for (int a = y; a <= 0; a++) {
//    DodajDo(suma, Get(0, a));
//  }
//  return suma;
}

int Prawo(int x) {
  assert(x >= 0);
  return Dodaj(Mnoz(4, SumujPot(x, 2)), Odejmij(SumujPot(x, 0), Mnoz(3, SumujPot(x, 1))));
//  int suma = 0;
//  for (int a = 0; a <= x; a++) {
//    DodajDo(suma, Get(a, 0));
//  }
//  return suma;
}

int Lewo(int x) {
  assert(x <= 0);
  return Dodaj(Mnoz(4, SumujPot(-x, 2)), Dodaj(SumujPot(-x, 1), SumujPot(-x, 0)));
//  int suma = 0;
//  for (int a = x; a <= 0; a++) {
//    DodajDo(suma, Get(a, 0));
//  }
//  return suma;
}

int Pionowy(int x1, int x2, int y1, int y2) {
  assert(x1 <= x2);
  assert(y1 <= y2);
  auto DajF = [x1](int y) {
    return [x1, y](int n) -> int {
      assert(0 <= n);
      return Get(x1 + n, y);
    };
  };
  Wiel f = Wiel::Interpoluj(DajF(y1), min(10, x2 - x1 + 1));
  Wiel g = Wiel::Interpoluj(DajF(y2), min(10, x2 - x1 + 1));
  Wiel sum = (f + g) * Podziel(y2 - y1 + 1, 2);
  return sum.PrefiksSum().Oblicz(x2 - x1);
//  int suma = 0;
//  for (int x = x1; x <= x2; x++) {
//    for (int y = y1; y <= y2; y++) {
//      DodajDo(suma, Get(x, y));
//    }
//  }
//  return suma;
}

int Poziomy(int x1, int x2, int y1, int y2) {
  assert(x1 <= x2);
  assert(y1 <= y2);
  auto DajF = [y1](int x) {
    return [x, y1](int n) -> int {
      assert(0 <= n);
      return Get(x, y1 + n);
    };
  };
  Wiel f = Wiel::Interpoluj(DajF(x1), min(10, y2 - y1 + 1));
  Wiel g = Wiel::Interpoluj(DajF(x2), min(10, y2 - y1 + 1));
  Wiel sum = (f + g) * Podziel(x2 - x1 + 1, 2);
  return sum.PrefiksSum().Oblicz(y2 - y1);
//  int suma = 0;
//  for (int x = x1; x <= x2; x++) {
//    for (int y = y1; y <= y2; y++) {
//      DodajDo(suma, Get(x, y));
//    }
//  }
//  return suma;
}

int PrawoGora2(int n) {
  assert(0 <= n);
  int suma = 0;
  for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
      DodajDo(suma, Get(a, b));
    }
  }
  return suma;
}

int PrawoGora(int x, int y) {
  assert(1 <= x);
  assert(1 <= y);
  if (x < y) {
    return Dodaj(PrawoGora(x, x), Poziomy(1, x, x + 1, y));
  }
  if (y < x) {
    return Dodaj(PrawoGora(y, y), Pionowy(y + 1, x, 1, y));
  }
  assert(x == y);
  static Wiel inter = Wiel::Interpoluj(PrawoGora2, 10);
  return inter.Oblicz(x);
}

int PrawoDol2(int n) {
  assert(0 <= n);
  int suma = 0;
  for (int a = 1; a <= n; a++) {
    for (int b = -n; b <= -1; b++) {
      DodajDo(suma, Get(a, b));
    }
  }
  return suma;
}

int PrawoDol(int x, int y) {
  assert(1 <= x);
  assert(y <= -1);
  if (x < -y) {
    return Dodaj(PrawoDol(x, -x), Poziomy(1, x, y, -x - 1));
  }
  if (-y < x) {
    return Dodaj(PrawoDol(-y, y), Pionowy(-y + 1, x, y, -1));
  }
  assert(x == -y);
  static Wiel inter = Wiel::Interpoluj(PrawoDol2, 10);
  return inter.Oblicz(x);
}

int LewoGora2(int n) {
  assert(0 <= n);
  int suma = 0;
  for (int a = -n; a <= -1; a++) {
    for (int b = 1; b <= n; b++) {
      DodajDo(suma, Get(a, b));
    }
  }
  return suma;
}

int LewoGora(int x, int y) {
  assert(x <= -1);
  assert(1 <= y);
  if (-x < y) {
    return Dodaj(LewoGora(x, -x), Poziomy(x, -1, -x + 1, y));
  }
  if (y < -x) {
    return Dodaj(LewoGora(-y, y), Pionowy(x, -y - 1, 1, y));
  }
  assert(-x == y);
  static Wiel inter = Wiel::Interpoluj(LewoGora2, 10);
  return inter.Oblicz(-x);
}

int LewoDol2(int n) {
  assert(0 <= n);
  int suma = 0;
  for (int a = -n; a <= -1; a++) {
    for (int b = -n; b <= -1; b++) {
      DodajDo(suma, Get(a, b));
    }
  }
  return suma;
}

int LewoDol(int x, int y) {
  assert(x <= -1);
  assert(y <= -1);
  if (-x < -y) {
    return Dodaj(LewoDol(x, x), Poziomy(x, -1, y, x - 1));
  }
  if (-y < -x) {
    return Dodaj(LewoDol(y, y), Pionowy(x, y - 1, y, -1));
  }
  assert(-x == -y);
  static Wiel inter = Wiel::Interpoluj(LewoDol2, 10);
  return inter.Oblicz(-x);
}

int Policz(int x1, int x2, int y1, int y2) {
  if (x2 < x1 or y2 < y1) return 0;
  debug() << "Policz(" imie(x1) imie(x2) imie(y1) imie(y2) ")";
  if (x1 <= 0 and 0 <= x2 and (x1 < 0 or 0 < x2)) {
    return Dodaj(Policz(x1, -1, y1, y2), Dodaj(Policz(0, 0, y1, y2), Policz(1, x2, y1, y2)));
  }
  if (y1 <= 0 and 0 <= y2 and (y1 < 0 or 0 < y2)) {
    return Dodaj(Policz(x1, x2, y1, -1), Dodaj(Policz(x1, x2, 0, 0), Policz(x1, x2, 1, y2)));
  }
  if (x1 == 0) {
    assert(x2 == 0);
    if (y1 == 0) {
      assert(y2 == 0);
      return 1;
    } else if (y1 > 0) {
      return Odejmij(Gora(y2), Gora(y1 - 1));
    } else {
      return Odejmij(Dol(y1), Dol(y2 + 1));
    }
  } else if (y1 == 0) {
    assert(y2 == 0);
    assert(x1 != 0);
    if (x1 > 0) {
      return Odejmij(Prawo(x2), Prawo(x1 - 1));
    } else {
      assert(x1 < 0);
      return Odejmij(Lewo(x1), Lewo(x2 + 1));
    }
  }
  assert(1 <= x1 or x2 <= -1);
  assert(1 <= y1 or y2 <= -1);

  if (1 < x1) return Odejmij(Policz(1, x2, y1, y2), Policz(1, x1 - 1, y1, y2));
  if (x2 < -1) return Odejmij(Policz(x1, -1, y1, y2), Policz(x2 + 1, -1, y1, y2));
  if (1 < y1) return Odejmij(Policz(x1, x2, 1, y2), Policz(x1, x2, 1, y1 - 1));
  if (y2 < -1) return Odejmij(Policz(x1, x2, y1, -1), Policz(x1, x2, y2 + 1, -1));

  assert(1 == x1 or x2 == -1);
  assert(1 == y1 or y2 == -1);

  if (x1 == 1 and y1 == 1) {
    return PrawoGora(x2, y2);
  } else if (x1 == 1 and y2 == -1) {
    return PrawoDol(x2, y1);
  } else if (x2 == -1 and y1 == 1) {
    return LewoGora(x1, y2);
  } else if (x2 == -1 and y2 == -1) {
    return LewoDol(x1, y1);
  }
  assert(false);
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;

  /*
  for (int i = 1; i <= n; i++) {
    debug() << imie(i) imie(PrawoGora2(i));
  }
  */

  while (q--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    cout << Policz(x1, x2, y1, y2) << endl;
  }
  return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25