Submission #645828

#	Time	Username	Problem	Language	Result	Execution time	Memory
645828		fatemetmhr	Spiral (BOI16_spiral)	C++17	31 / 100	1 ms	212 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 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;
}

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;
}

inline ll moraba(ll n){
    return (2 * mod + (8 * sigmai3(n) % mod) - (8 * sigmai2(n) % mod) + (4 * sigmai(n) % mod) - (n % mod)) % mod;
}

inline ll sumio1(ll n){
    return (mod + (4 * sigmai2(n) % mod) - (3 * sigmai(n) % mod) + (2 * n % mod)) % mod;
}

inline ll sum1oi(ll n){
    return (mod + (4 * sigmai2(n) % mod) - sigmai(n)) % mod;
}

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 = moraba(min(x2, y2));
        if(y2 < x2){
            ll A = (sumio1(x2) - sumio1(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 = (sum1oi(y2) - sum1oi(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;
        }
        cout << ans << '\n';
    }
}

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