Submission #51332

#	Time	Username	Problem	Language	Result	Execution time	Memory
51332		mareksom	Spiral (BOI16_spiral)	C++17	27 / 100	1588 ms	560 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); }

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) {
  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 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);
  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 main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  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: 0 / 17
• Subtask 4: 0 / 31
• Subtask 5: 0 / 25