Submission #645863

#	Time	Username	Problem	Language	Result	Execution time	Memory
645863		fatemetmhr	Spiral (BOI16_spiral)	C++17	100 / 100	1 ms	324 KiB

spiral

//  ~ 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';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25