oj.uz

Submission #516674

# Submission time Handle Problem Language Result Execution time Memory
516674 2022-01-21T18:48:59 Z _martynas Spiral (BOI16_spiral) C++11
31 / 100
 1 ms 416 KB 
// 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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 416 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -