Submission #516674

#	Time	Username	Problem	Language	Result	Execution time	Memory
516674		_martynas	Spiral (BOI16_spiral)	C++11	31 / 100	1 ms	416 KiB

spiral

// Subtask 4
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll MOD = 1e9+7;

int n, q;

ll quickPow(ll x, ll y)
{
    ll ans = 1;
    while(y) {
        if(y & 1) {
            ans *= x;
            ans %= MOD;
        }
        y >>= 1;
        x *= x;
        x %= MOD;
    }
    return ans;
}

ll add(ll x, ll y)
{
    return (((x+y)%MOD)+MOD)%MOD;
}

ll sub(ll x, ll y)
{
    return add(x, -y);
}

ll mul(ll x, ll y)
{
    return x*y%MOD;
}

ll dvd(ll x, ll y)
{
    return x*quickPow(y,MOD-2)%MOD;
}

ll get1(ll x1, ll y1, ll x2, ll y2)
{
    if(x2 < x1 || y2 < y1) return 0LL;
    x1 = max(x1, 1LL);
    y1 = max(y1, 1LL);
    ll n = y2-y1+1;
    ll m = x2-x1+1;
    ll ans = 0;

    // 2*n*m
    ans = add(ans, mul(mul(n, m), 2));

    // squares
    ll nn = min(n, m);

    // n*(2*n-1)*(2*n+1) / 3
    ans = add(ans, dvd(mul(nn, mul(sub(mul(2, nn), 1), add(mul(2, nn), 1))), 3));
    // 8 * ( n^2*(n-1)*(n+1) / 4 )
    ans = add(ans, mul(8, dvd(mul(mul(nn, nn), mul(sub(nn, 1), add(nn, 1))), 4)));

    // rectangles
    if(n > m) {
        // m * ( n*(3*n-1) / 2 - m*(3*m-1) / 2) - (n-m)*m*(m-1)/2
        ans = add(ans,
            mul(m,
                sub(dvd(mul(n, sub(mul(3, n), 1)), 2),
                    dvd(mul(m, sub(mul(3, m), 1)), 2))
            ));
        ans = sub(ans, dvd(mul(sub(n, m), mul(m, sub(m, 1))), 2));

        // 8 * m * ( n*(n-1)*(n+1) / 6 - m*(m-1)*(m+1) / 6 )
        ans = add(ans,
            mul(mul(8, m),
                sub(dvd(mul(n, mul(sub(n, 1), add(n, 1))), 6),
                    dvd(mul(m, mul(sub(m, 1), add(m, 1))), 6))));
    }
    else if(m > n) {
        // n * ( m*(m+1) / 2 - n*(n+1) / 2) + (m-n)*n*(n-1)/2
        ans = add(ans,
            mul(n,
                sub(dvd(mul(m, add(m, 1)), 2),
                    dvd(mul(n, add(n, 1)), 2))
            ));
        ans = add(ans, dvd(mul(sub(m, n), mul(n, sub(n, 1))), 2));

        // 8 * n * ( m*(m-1)*(m+1) / 6 - n*(n-1)*(n+1) / 6 )
        ans = add(ans,
            mul(mul(8, n),
                sub(dvd(mul(m, mul(sub(m, 1), add(m, 1))), 6),
                    dvd(mul(n, mul(sub(n, 1), add(n, 1))), 6))));
    }

    return ans;
}

int main()
{
    cin >> n >> q;

    for(int k = 0; k < q; k++) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        assert(x1 == 1 && y1 == 1);
        cout << get1(x1, y1, x2, y2) << "\n";
    }

    return 0;
}
/*

10000 2
1 1 3 1
1 1 4 1
out: 44, 98 ok

10000 2
1 1 1 3
1 1 1 4
out: 50, 110 ok

10000 2
1 1 3 3
1 1 4 4
out: 197, 596 ok


10000 2
1 1 2 6
1 1 6 2
out: 690, 642 ok
*/

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