#include <bits/stdc++.h>
using namespace std;
#define int __int128
using ll = long long;
int modulo = 1e9 + 7;
int dreapta_sus(int x,int y)
{
///de la 1 la x si de la 1 la y
int d = min(x,y);
if (d <= 0)
return 0;
int s = -d + 2 * d * d * (d + 1) * (d + 1) - 2 * d * (d + 1) * (2 * d + 1) + 3 * d * (d + 1) + 4 * d * (d + 1) * (2 * d + 1) / 6 - d * (d + 1);
s %= modulo;
if (x == y)
return s;
else if (x > y)
{
int s2 = (x - y) * y * (y + 1) / 2 + y * x * (x + 1) / 2 - y * y * (y + 1) / 2 + y * (x - y) + 4 * y * x * (x + 1) * (2 * x + 1) / 6 - 4 * y * y * (y + 1) * (2 * y + 1) / 6 - 4 * y * x * (x + 1) / 2 + 4 * y * y * (y + 1) / 2;
s += s2;
s %= modulo;
return s;
}
else
{
int s2 = x * (y - x) + 4 * x * y * (y + 1) * (2 * y + 1) / 6 - 4 * x * x * (x + 1) * (2 * x + 1) / 6 + 2 * x * x * (x + 1) - 2 * x * y * (y + 1) + x * y * (y + 1) - x * x * (x + 1) - (y - x) * x * x + x * y * (y + 1) / 2 - x * x * (x + 1) / 2 + (y - x) * x * (x - 1) / 2;
s += s2;
s %= modulo;
return s;
}
}
int stanga_sus(int x,int y)///atentie la semne!!
{
///de la -x la -1 si de la 1 la y
int d = min(x,y);
if (d <= 0)
return 0;
int s = dreapta_sus(x,y) + 2 * d * (d + 1) * (2 * d + 1) / 3 - d * (d + 1);
s %= modulo;
if (x == y)
return s;
else if (x > y)
{
int s2 = (x - y) * y * (-y - 1) + 2 * y * x * (x + 1) - 2 * y * y * (y + 1);
s += s2;
s %= modulo;
return s;
}
else
{
int s2 = x * (y - x) * (x + 1);
s += s2;
s %= modulo;
return s;
}
}
int stanga_jos(int x,int y)///atentie la semne!!
{
///de la -x la -1 si de la -y la -1
int d = min(x,y);
if (d <= 0)
return 0;
int s = dreapta_sus(x,y) + 4 * d * (d + 1) * (2 * d + 1) / 3 - 2 * d * (d + 1);
if (x == y)
return s;
else if (x > y)
{
int s2 = 2 * y * x * (x + 1) - 2 * y * y * (y + 1);
s += s2;
//cout << (ll)s2 << endl;
s %= modulo;
return s;
}
else
{
int s2 = 2 * x * y * (y + 1) - 2 * x * x * (x + 1);
s += s2;
s %= modulo;
return s;
}
}
int dreapta_jos(int x,int y)
{
///de la 1 la x si de la -1 la -y
int d = min(x,y);
if (d <= 0)
return 0;
int s = 2 * d * d * (d - 1) * (d - 1) + 4 * (d - 1) * d * (2 * d - 1) / 3 + d * (d - 1) + d * (2 * d + 1) * (2 * d + 1);
//cout << (ll)s << endl;
s %= modulo;
if (x == y)
return s;
else if (x > y)
{
int s2 = (x - y) * y + (x - y) * y * (y - 1) / 2 - (x - y) * y * y + y * x * (x + 1) / 2 - y * y * (y + 1) / 2 + 2 * y * x * (x + 1) * (2 * x + 1) / 3 - 2 * y * y * (y + 1) * (2 * y + 1) / 3 - 2 * y * x * (x + 1) + 2 * y * y * (y + 1);
s += s2;
s %= modulo;
return s;
}
else
{
int s2 = -(y - x) * x * (x - 1) / 2 + (y - x) * x * x - x * y * (y + 1) / 2 + x * x * (x + 1) / 2 + (y - x) * x + 2 * x * y * (y + 1) - 2 * x * x * (x + 1) + 2 * x * y * (y + 1) * (2 * y + 1) / 3 - 2 * x * x * (x + 1) * (2 * x + 1) / 3;
s += s2;
s %= modulo;
return s;
}
}
int dreapta(int x)
{
///de la 1 la x, cu y = 0
int s = x * (x + 1) / 2 + x - 2 * x * (x + 1) + 2 * x * (x + 1) * (2 * x + 1) / 3;
s %= modulo;
return s;
}
int stanga(int x)
{
///de la -x la -1, cu y = 0
int s = dreapta(x) + 2 * x * (x + 1);
s %= modulo;
return s;
}
int sus(int y)
{
///de la 1 la y, cu x = 0
int s = dreapta(y) + y * (y + 1);
s %= modulo;
return s;
}
int jos(int y)
{
///de la -y la -1, cu x = 0
int s = dreapta(y) + 3 * y * (y + 1);
s %= modulo;
return s;
}
int ri(int l,int r)
{
return l + rand() % (r - l + 1);
}
map<pair<int,int>,int> mat;
int ans_brut(int x1,int y1,int x2,int y2)
{
int sm = 0;
for (int i = x1; i <= x2; i++)
for (int j = y1; j <= y2; j++)
sm += mat[{i,j}];//cout << (ll)mat[{i,j}] << endl;
return sm % modulo;
}
void testcase()
{
ll X1,Y1,X2,Y2;
cin >> X1 >> Y1 >> X2 >> Y2;
/*X1 = ri(-3,3);
Y1 = ri(-3,3);
X2 = ri(X1,3);
Y2 = ri(Y1,3);*/
int x1 = X1,x2 = X2,y1 = Y1,y2 = Y2;
int ans = 0;
if (x1 <= 0 and x2 >= 0 and y1 <= 0 and y2 >= 0)
ans = 1;
if (x1 <= 0 and x2 >= 0)
{
if (y1 > 0)
ans += sus(y2) - sus(y1 - 1);
else if (y2 < 0)
ans += jos(-y1) - jos(-y2 - 1);
else
ans += sus(y2) + jos(-y1);
}
if (y1 <= 0 and y2 >= 0)
{
if (x1 > 0)
ans += dreapta(x2) - dreapta(x1 - 1);
else if (x2 < 0)
ans += stanga(-x1) - stanga(-x2 - 1);
else
ans += dreapta(x2) + stanga(-x1);
}
//cout << (ll)ans << endl;
int gx1,gx2,gy1,gy2;
gx1 = max(1ll,(ll)x1);
gx2 = x2;
gy1 = max(1ll,(ll)y1);
gy2 = y2;
if (gx2 >= gx1 and gy2 >= gy1)
{
ans += dreapta_sus(gx2,gy2) + dreapta_sus(gx1 - 1,gy1 - 1) - dreapta_sus(gx2,gy1 - 1) - dreapta_sus(gx1 - 1,gy2);
}
//cout << (ll)ans << endl;
gx1 = x1;
gx2 = min((ll)x2,-1ll);
if (gx2 >= gx1 and gy2 >= gy1)
{
ans += stanga_sus(-gx1,gy2) + stanga_sus(-gx2 - 1,gy1 - 1) - stanga_sus(-gx1,gy1 - 1) - stanga_sus(-gx2 - 1,gy2);
///(3,3) - (3,1)
}
//cout << (ll)stanga_sus(3,3) << ' ' << (ll)stanga_sus(3,1) << endl;
//cout << (ll)ans << endl;
gy1 = y1;
gy2 = min((ll)y2,-1ll);
if (gx2 >= gx1 and gy2 >= gy1)
{
ans += stanga_jos(-gx1,-gy1) + stanga_jos(-gx2 - 1,-gy2 - 1) - stanga_jos(-gx1,-gy2 - 1) - stanga_jos(-gx2 - 1,-gy1);
}
//cout << (ll)ans << endl;
gx1 = max(1ll,(ll)x1);
gx2 = x2;
//cout << (ll)gx1 << ' ' << (ll)gy1 << ' ' << (ll)gx2 << ' ' << (ll)gy2 << endl;
if (gx2 >= gx1 and gy2 >= gy1)
{
ans += dreapta_jos(gx2,-gy1) + dreapta_jos(gx1 - 1,-gy2 - 1) - dreapta_jos(gx2,-gy2 - 1) - dreapta_jos(gx1 - 1,-gy1);
}
//cout << (ll)dreapta_jos(3,2) << endl;
//cout << (ll)ans << endl;
ans += modulo * modulo;
ans %= modulo;
ans += modulo;
ans %= modulo;
cout << (ll)ans << '\n';
//cout << (ll)ans_brut(X1,Y1,X2,Y2) << '\n';
}
///0 -2 3 2
vector<vector<int>> mt;
signed main()
{
ll n,tc;
cin >> n >> tc;
while (tc--)
testcase();
return 0;
}
///-3 2 2 3
/**
cea mai de mate de a 5a problema
**/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
