Submission #645863

#TimeUsernameProblemLanguageResultExecution timeMemory
645863fatemetmhrSpiral (BOI16_spiral)C++17
100 / 100
1 ms324 KiB
// ~ Be Name Khoda ~ // #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define mp make_pair #define all(x) x.begin(), x.end() #define fi first #define se second const int maxn = 1e6 + 10; const int maxn5 = 5e5 + 10; const int maxnt = 1.2e6 + 10; const int maxn3 = 1e3 + 10; const int mod = 1e9 + 7; const ll inf = 1e18; ll tagh2, tagh6; inline ll max(ll a, int b){ return max(a, ll(b)); } inline ll min(ll a, int b){ return min(a, ll(b)); } inline ll pw(ll a, ll b){ ll ret = 1; a %= mod; for(; b; b >>= 1, a = a * a % mod) if(b&1) ret = ret * a % mod; return ret; } // ----------------------SGIMA---------------------- inline ll sigmai(ll n){ n %= mod; return (n * (n + 1) % mod) * tagh2 % mod; } inline ll sigmai2(ll n){ n %= mod; return ((n * (n + 1) % mod) * ((2 * n + 1) % mod) % mod) * tagh6 % mod; } inline ll sigmai3(ll n){ n %= mod; ll ans = (n * (n + 1) % mod) * tagh2 % mod; return ans * ans % mod; } // ----------------------MORABA---------------------- inline ll moraba1(ll n){ return (2 * mod + (8 * sigmai3(n) % mod) - (8 * sigmai2(n) % mod) + (4 * sigmai(n) % mod) - (n % mod)) % mod; } inline ll moraba2(ll n){ return (2 * mod + (8 * sigmai3(n) % mod) - (12 * sigmai2(n) % mod) + (8 * sigmai(n) % mod) - (2 * n % mod)) % mod; } inline ll moraba3(ll n){ return (2 * mod + (8 * sigmai3(n) % mod) - (16 * sigmai2(n) % mod) + (12 * sigmai(n) % mod) - (3 * n % mod)) % mod; } inline ll moraba4(ll n){ return (2 * mod + (8 * sigmai3(n) % mod) - (4 * sigmai2(n) % mod) + (2 * sigmai(n) % mod) - (n % mod)) % mod; } // ----------------------SUM KHAT---------------------- inline ll sumio11(ll n){ return (mod + (4 * sigmai2(n) % mod) - (3 * sigmai(n) % mod) + (2 * n % mod)) % mod; } inline ll sum1oi1(ll n){ return (mod + (4 * sigmai2(n) % mod) - sigmai(n)) % mod; } inline ll sumio02(ll n){ return (mod + (4 * sigmai2(n) % mod) - (3 * sigmai(n) % mod) + (n % mod)) % mod; } inline ll sum1oi2(ll n){ return (mod + (4 * sigmai2(n) % mod) - (5 * sigmai(n) % mod) + (3 * n % mod)) % mod; } inline ll sumio03(ll n){ return (mod + (4 * sigmai2(n) % mod) - (7 * sigmai(n) % mod) + (4 * n % mod)) % mod; } inline ll sum0oi3(ll n){ return (mod + (4 * sigmai2(n) % mod) - (5 * sigmai(n) % mod) + (2 * n % mod)) % mod; } inline ll sumio14(ll n){ return (mod + (4 * sigmai2(n) % mod) + (sigmai(n) % mod)) % mod; } inline ll sum1oi4(ll n){ return (mod + (4 * sigmai2(n) % mod) - (sigmai(n) % mod) + (2 * n % mod)) % mod; } inline ll sum0oi5(ll n){ return (mod + (4 * sigmai2(n) % mod) - (sigmai(n) % mod) + (n % mod)) % mod; } // ----------------------GET---------------------- inline ll get1(ll x2, ll y2){ ll ans = moraba1(min(x2, y2)); if(y2 < x2){ ll A = (sumio11(x2) - sumio11(y2) + mod) % mod; ll d = x2 - y2; d %= mod; ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } if(y2 > x2){ ll A = (sum1oi1(y2) - sum1oi1(x2) + mod) % mod; ll d = (x2 % mod) - (y2 % mod) + mod; d %= mod; ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } return ans; } inline ll get2(ll x2, ll y2){ y2 *= -1; y2++; ll ans = moraba2(min(x2, y2)); if(y2 < x2){ ll A = (sumio02(x2) - sumio02(y2) + mod) % mod; ll d = mod + (y2 % mod) - (x2 % mod); d %= mod; ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } if(y2 > x2){ ll A = (sum1oi2(y2) - sum1oi2(x2) + mod) % mod; ll d = (y2 % mod) - (x2 % mod) + mod; d %= mod; ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } return ans; } inline ll get3(ll x2, ll y2){ y2 *= -1; y2++; x2 *= -1; x2++; ll ans = moraba3(min(x2, y2)); if(y2 < x2){ ll A = (sumio03(x2) - sumio03(y2) + mod) % mod; ll d = mod + (x2 % mod) - (y2 % mod); d %= mod; ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } if(y2 > x2){ ll A = (sum0oi3(y2) - sum0oi3(x2) + mod) % mod; ll d = (x2 % mod) - (y2 % mod) + mod; d %= mod; ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } return ans; } inline ll get4(ll x2, ll y2){ x2 *= -1; ll ans = moraba4(min(x2, y2)); if(y2 < x2){ ll A = (sumio14(x2) - sumio14(y2) + mod) % mod; ll d = mod + (y2 % mod) - (x2 % mod); d %= mod; ans += (y2 * ((2 * A + ((y2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } if(y2 > x2){ ll A = (sum1oi4(y2) - sum1oi4(x2) + mod) % mod; ll d = (y2 % mod) - (x2 % mod) + mod; d %= mod; ans += (x2 * ((2 * A + ((x2 - 1) * d % mod)) % mod) % mod) * tagh2 % mod; ans %= mod; } return ans; } // ----------------------MANTAGHE---------------------- inline ll mantaghe1(ll x1, ll y1, ll x2, ll y2){ if(x2 < 1) return 0; if(y2 < 1) return 0; x1 = max(x1, 1); y1 = max(y1, 1); ll ans = get1(x2, y2); if(x1 > 1) ans = (ans + mod - get1(x1 - 1, y2)) % mod; if(y1 > 1) ans = (ans + mod - get1(x2, y1 - 1)) % mod; if(x1 > 1 && y1 > 1) ans = (ans + get1(x1 - 1, y1 - 1)) % mod; return ans; } inline ll mantaghe2(ll x1, ll y1, ll x2, ll y2){ if(x2 < 1) return 0; if(y1 > 0) return 0; x1 = max(x1, 1); y2 = min(y2, 0); swap(y1, y2); ll ans = get2(x2, y2); if(x1 > 1) ans = (ans + mod - get2(x1 - 1, y2)) % mod; if(y1 < 0) ans = (ans + mod - get2(x2, y1 + 1)) % mod; if(x1 > 1 && y1 < 0) ans = (ans + get2(x1 - 1, y1 + 1)) % mod; return ans; } inline ll mantaghe3(ll x1, ll y1, ll x2, ll y2){ if(x1 > 0) return 0; if(y1 > 0) return 0; x2 = min(x2, 0); y2 = min(y2, 0); swap(y1, y2); swap(x1, x2); ll ans = get3(x2, y2); if(x1 < 0) ans = (ans + mod - get3(x1 + 1, y2)) % mod; if(y1 < 0) ans = (ans + mod - get3(x2, y1 + 1)) % mod; if(x1 < 0 && y1 < 0) ans = (ans + get3(x1 + 1, y1 + 1)) % mod; return ans; } inline ll mantaghe4(ll x1, ll y1, ll x2, ll y2){ if(x1 > -1) return 0; if(y2 < 1) return 0; x2 = min(x2, -1); y1 = max(y1, 1); swap(x1, x2); ll ans = get4(x2, y2); if(x1 < -1) ans = (ans + mod - get4(x1 + 1, y2)) % mod; if(y1 > 1) ans = (ans + mod - get4(x2, y1 - 1)) % mod; if(x1 < -1 && y1 > 1) ans = (ans + get4(x1 + 1, y1 - 1)) % mod; return ans; } inline ll mantaghe5(ll x1, ll y1, ll x2, ll y2){ if(x1 > 0 || x2 < 0) return 0; if(y2 < 1) return 0; x1 = x2 = 0; y1 = max(y1, 1); return (sum0oi5(y2) - (y1 == 1 ? 0 : sum0oi5(y1 - 1)) + mod) % mod; } // ----------------------MAIN---------------------- int main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); tagh2 = pw(2, mod - 2); tagh6 = pw(6, mod - 2); ll n; int tt; cin >> n >> tt; while(tt--){ ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; ll ans = mantaghe1(x1, y1, x2, y2); ans = (ans + mantaghe2(x1, y1, x2, y2)) % mod; ans = (ans + mantaghe3(x1, y1, x2, y2)) % mod; ans = (ans + mantaghe4(x1, y1, x2, y2)) % mod; ans = (ans + mantaghe5(x1, y1, x2, y2)) % mod; cout << ans << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...