#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;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
497 ms |
248 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
497 ms |
248 KB |
Output is correct |
| 2 |
Execution timed out |
1579 ms |
560 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1588 ms |
560 KB |
Time limit exceeded |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
497 ms |
248 KB |
Output is correct |
| 2 |
Correct |
2 ms |
356 KB |
Output is correct |
| 3 |
Execution timed out |
1579 ms |
560 KB |
Time limit exceeded |
