Submission #517215

#	Time	Username	Problem	Language	Result	Execution time	Memory
517215		_martynas	Spiral (BOI16_spiral)	C++11	100 / 100	2 ms	292 KiB

spiral

#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, ll base, bool swapNM)
{
    if(x2 < x1 || y2 < y1) return 0LL;
    ll n = y2-y1+1;
    ll m = x2-x1+1;
    ll ans = 0;

    if(swapNM) swap(n, m);

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

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

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

    if(n < m) swap(n, m);

    // square
    // (m*(m-1)*(4*m+1)) / 6
    ans = add(ans, dvd(mul(m, mul(sub(m, 1), add(mul(4, m), 1))), 6LL));

    // rectangle
    if(n != m) {
        // m * ( n*(n-1)/2 - m*(m-1)/2 )
        ans = add(ans, mul(m,
            sub(dvd(mul(n, sub(n, 1)), 2),
                dvd(mul(m, sub(m, 1)), 2))));
    }

    // ans *= base;
    ans = mul(ans, base);
    return ans;
}

ll get3(ll m, ll base, ll init)
{
    if(m <= 0) return 0LL;
    ll ans = 0;
    // init * m
    ans = add(ans, mul(init, m));
    // base * ( m*(m-1) / 2 )
    ans = add(ans, mul(base, dvd(mul(m, sub(m, 1)), 2)));
    // 8 * ( m*(m-1)*(m-2) / 6 )
    ans = add(ans, mul(8, dvd(mul(m, mul(sub(m, 2), sub(m, 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;
        ll ans = 0;

        // corner 3
        if(x2 >= 1 && y2 >= 1) {
            if(x1 <= 1 && y1 <= 1) {
                //cerr << get1(max(x1, 1LL), max(y1, 1LL), x2, y2, 2, false) << "\n";
                ans = add(ans, get1(1, 1, x2, y2, 2, false));
            }
            else if(x1 > 1 && y1 <= 1) {
                ans = add(ans, get1(1, 1, x2, y2, 2, false));
                ans = sub(ans, get1(1, 1, x1-1, y2, 2, false));
            }
            else if(x1 <= 1 && y1 > 1) {
                ans = add(ans, get1(1, 1, x2, y2, 2, false));
                ans = sub(ans, get1(1, 1, x2, y1-1, 2, false));
            }
            else {
                ans = add(ans, get1(1, 1, x2, y2, 2, false));
                ans = add(ans, get1(1, 1, x1-1, y1-1, 2, false));
                ans = sub(ans, get1(1, 1, x1-1, y2, 2, false));
                ans = sub(ans, get1(1, 1, x2, y1-1, 2, false));
            }
        }

        // corner 5
        if(x1 <= -1 && y2 >= 1) {
            if(x2 >= -1 && y1 <= 1) {
                //cerr << get1(x1, max(y1, 1LL), min(x2, -1LL), y2, 4, true) << "\n";
                ans = add(ans, get1(x1, 1, -1, y2, 4, true));

                //cerr << get2(x1, max(y1, 1LL), min(x2, -1LL), y2, 2) << "\n";
                ans = add(ans, get2(x1, 1, -1, y2, 2));
            }
            else if(x2 < -1 && y1 <= 1) {
                ans = add(ans, get1(x1, 1, -1, y2, 4, true));
                ans = sub(ans, get1(x2+1, 1, -1, y2, 4, true));

                ans = add(ans, get2(x1, 1, -1, y2, 2));
                ans = sub(ans, get2(x2+1, 1, -1, y2, 2));
            }
            else if(x2 >= -1 && y1 > 1) {
                ans = add(ans, get1(x1, 1, -1, y2, 4, true));
                ans = sub(ans, get1(x1, 1, -1, y1-1, 4, true));

                ans = add(ans, get2(x1, 1, -1, y2, 2));
                ans = sub(ans, get2(x1, 1, -1, y1-1, 2));
            }
            else {
                ans = add(ans, get1(x1, 1, -1, y2, 4, true));
                ans = add(ans, get1(x2+1, 1, -1, y1-1, 4, true));
                ans = sub(ans, get1(x2+1, 1, -1, y2, 4, true));
                ans = sub(ans, get1(x1, 1, -1, y1-1, 4, true));

                ans = add(ans, get2(x1, 1, -1, y2, 2));
                ans = add(ans, get2(x2+1, 1, -1, y1-1, 2));
                ans = sub(ans, get2(x2+1, 1, -1, y2, 2));
                ans = sub(ans, get2(x1, 1, -1, y1-1, 2));
            }
        }

        // corner 7
        if(x1 <= -1 && y1 <= -1) {
            if(x2 >= -1 && y2 >= -1) {
                //cerr << get1(x1, y1, min(x2, -1LL), min(y2, -1LL), 6, false) << "\n";
                ans = add(ans, get1(x1, y1, -1, -1, 6, false));

                //cerr << get2(x1, y1, min(x2, -1LL), min(y2, -1LL), 4) << "\n";
                ans = add(ans, get2(x1, y1, -1, -1, 4));
            }
            else if(x2 < -1 && y2 >= -1) {
                ans = add(ans, get1(x1, y1, -1, -1, 6, false));
                ans = sub(ans, get1(x2+1, y1, -1, -1, 6, false));

                ans = add(ans, get2(x1, y1, -1, -1, 4));
                ans = sub(ans, get2(x2+1, y1, -1, -1, 4));
            }
            else if(x2 >= -1 && y2 < -1) {
                ans = add(ans, get1(x1, y1, -1, -1, 6, false));
                ans = sub(ans, get1(x1, y2+1, -1, -1, 6, false));

                ans = add(ans, get2(x1, y1, -1, -1, 4));
                ans = sub(ans, get2(x1, y2+1, -1, -1, 4));
            }
            else {
                ans = add(ans, get1(x1, y1, -1, -1, 6, false));
                ans = add(ans, get1(x2+1, y2+1, -1, -1, 6, false));
                ans = sub(ans, get1(x2+1, y1, -1, -1, 6, false));
                ans = sub(ans, get1(x1, y2+1, -1, -1, 6, false));

                ans = add(ans, get2(x1, y1, -1, -1, 4));
                ans = add(ans, get2(x2+1, y2+1, -1, -1, 4));
                ans = sub(ans, get2(x2+1, y1, -1, -1, 4));
                ans = sub(ans, get2(x1, y2+1, -1, -1, 4));
            }
        }

        // corner 10
        if(x2 >= 2 && y1 <= -1) {
            if(x1 <= 2 && y2 >= -1) {
                //cerr << get1(max(x1, 2LL), y1, x2, min(y2, -1LL), 9, true) << "\n";
                ans = add(ans, get1(2, y1, x2, -1, 9, true));

                //cerr << get2(max(x1, 2LL), y1, x2, min(y2, -1LL), 6) << "\n";
                ans = add(ans, get2(2, y1, x2, -1, 6));
            }
            else if(x1 > 2 && y2 >= -1) {
                ans = add(ans, get1(2, y1, x2, -1, 9, true));
                ans = sub(ans, get1(2, y1, x1-1, -1, 9, true));

                ans = add(ans, get2(2, y1, x2, -1, 6));
                ans = sub(ans, get2(2, y1, x1-1, -1, 6));
            }
            else if(x1 <= 2 && y2 < -1) {
                ans = add(ans, get1(2, y1, x2, -1, 9, true));
                ans = sub(ans, get1(2, y2+1, x2, -1, 9, true));

                ans = add(ans, get2(2, y1, x2, -1, 6));
                ans = sub(ans, get2(2, y2+1, x2, -1, 6));
            }
            else {
                ans = add(ans, get1(2, y1, x2, -1, 9, true));
                ans = add(ans, get1(2, y2+1, x1-1, -1, 9, true));
                ans = sub(ans, get1(2, y1, x1-1, -1, 9, true));
                ans = sub(ans, get1(2, y2+1, x2, -1, 9, true));

                ans = add(ans, get2(2, y1, x2, -1, 6));
                ans = add(ans, get2(2, y2+1, x1-1, -1, 6));
                ans = sub(ans, get2(2, y1, x1-1, -1, 6));
                ans = sub(ans, get2(2, y2+1, x2, -1, 6));
            }
        }

        // 4 and up
        if(x1 <= 0 && 0 <= x2) {
            //cerr << sub(get3(y2, 11, 4), get3(y1-1, 11, 4)) << "\n";
            ans = add(ans, sub(get3(y2, 11, 4), get3(y1-1, 11, 4)));
        }

        // 6 and left
        if(y1 <= 0 && 0 <= y2) {
            //cerr << sub(get3(-x1, 13, 6), get3((-x2)-1, 13, 6)) << "\n";
            ans = add(ans, sub(get3(-x1, 13, 6), get3((-x2)-1, 13, 6)));
        }

        // 8 and down
        if(x1 <= 0 && 0 <= x2) {
            //cerr << sub(get3(-y1, 15, 8), get3((-y2)-1, 15, 8)) << "\n";
            ans = add(ans, sub(get3(-y1, 15, 8), get3((-y2)-1, 15, 8)));
        }

        // 9 and down
        if(x1 <= 1 && 1 <= x2) {
            //cerr << sub(get3(-y1, 15, 9), get3((-y2)-1, 15, 9)) << "\n";
            ans = add(ans, sub(get3(-y1, 15, 9), get3((-y2)-1, 15, 9)));
        }

        // 2 and right
        if(y1 <= 0 && 0 <= y2) {
            //cerr << sub(get3(x2, 9, 2), get3(x1-1, 9, 2)) << "\n";
            ans = add(ans, sub(get3(x2, 9, 2), get3(x1-1, 9, 2)));
        }

        // 1
        if(x1 <= 0 && 0 <= x2 && y1 <= 0 && 0 <= y2) {
            //cerr << "1\n";
            ans = add(ans, 1);
        }

        cout << ans << "\n";

        cerr << "-----------\n";
    }

    return 0;
}
/*
10000 5
-69 69 420 420
-69 420 69 420
69 0 420 69
-69 0 420 69
-420 0 420 69
out: 498496110, 98020159, 892399318, 984401158, 897862664 ok


10000 1
-5 -2 -3 3
out: 1281 ok

10000 3
2 2 3 3
2 1 3 3
1 2 3 3
out: 106, 147, 153 ok

10000 3
-3 2 -2 3
-3 1 -2 3
-3 2 -1 3
out: 128, 185, 179 ok

10000 3
-3 -3 -2 -2
-3 -3 -2 -1
-3 -3 -1 -2
out: 150, 211, 217 ok

10000 3
3 -3 4 -2
3 -3 4 -1
2 -3 4 -2
out: 176, 255, 249 ok

10000 5
-3 -3 -1 -1
-3 -1 -1 -1
-1 -3 -1 -1
-3 -5 -1 -1
-5 -3 -1 -1
out: 285, 68, 74, 852, 822 ok

10000 5
-3 -3 -1 0
-3 -1 -1 0
-1 -3 -1 0
-3 -5 -1 0
-5 -3 -1 0
out: 350, 133, 80, 917, 1062 ok

10000 2
-5 0 -3 0
-3 0 -1 0
out: 215, 65 ok

10000 1
-2 -2 2 2
out: 325 ok

10000 1
-10 -10 10 10
out: 97461 ok

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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25