#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) {
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) {
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 PrawoDol(int x, int y) {
assert(1 <= x);
assert(y <= -1);
int suma = 0;
for (int a = 1; a <= x; a++) {
for (int b = y; b <= -1; b++) {
DodajDo(suma, Get(a, b));
}
}
return suma;
}
int LewoGora(int x, int y) {
assert(x <= -1);
assert(1 <= y);
int suma = 0;
for (int a = x; a <= -1; a++) {
for (int b = 1; b <= y; b++) {
DodajDo(suma, Get(a, b));
}
}
return suma;
}
int LewoDol(int x, int y) {
assert(x <= -1);
assert(y <= -1);
int suma = 0;
for (int a = x; a <= -1; a++) {
for (int b = y; b <= -1; b++) {
DodajDo(suma, Get(a, b));
}
}
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);
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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
752 ms |
340 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1569 ms |
488 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
752 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1569 ms |
488 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
13 ms |
488 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
752 ms |
340 KB |
Output is correct |
| 2 |
Execution timed out |
1569 ms |
488 KB |
Time limit exceeded |
