Submission #987914

#	Time	Username	Problem	Language	Result	Execution time	Memory
987914		andrei_iorgulescu	Spiral (BOI16_spiral)	C++14	31 / 100	1 ms	348 KiB

spiral

#include <bits/stdc++.h>

using namespace std;

#define int __int128
using ll = long long;

int modulo = 1e9 + 7;

int dreapta_sus(int x,int y)
{
    ///de la 1 la x si de la 1 la y
    int d = min(x,y);
    if (d <= 0)
        return 0;
    int s = -d + 2 * d * d * (d + 1) * (d + 1) - 2 * d * (d + 1) * (2 * d + 1) + 3 * d * (d + 1) + 4 * d * (d + 1) * (2 * d + 1) / 6 - d * (d + 1);
    s %= modulo;
    if (x == y)
        return s;
    else if (x > y)
    {
        int s2 = (x - y) * y * (y + 1) / 2 + y * x * (x + 1) / 2 - y * y * (y + 1) / 2 + y * (x - y) + 4 * y * x * (x + 1) * (2 * x + 1) / 6 - 4 * y * y * (y + 1) * (2 * y + 1) / 6 - 4 * y * x * (x + 1) / 2 + 4 * y * y * (y + 1) / 2;
        s += s2;
        s %= modulo;
        return s;
    }
    else
    {
        int s2 = x * (y - x) + 4 * x * y * (y + 1) * (2 * y + 1) / 6 - 4 * x * x * (x + 1) * (2 * x + 1) / 6 + 2 * x * x * (x + 1) - 2 * x * y * (y + 1) + x * y * (y + 1) - x * x * (x + 1) - (y - x) * x * x + x * y * (y + 1) / 2 - x * x * (x + 1) / 2 + (y - x) * x * (x - 1) / 2;
        s += s2;
        s %= modulo;
        return s;
    }
}

int stanga_sus(int x,int y)///atentie la semne!!
{
    ///de la -x la -1 si de la 1 la y
    int d = min(x,y);
    if (d <= 0)
        return 0;
    int s = dreapta_sus(x,y) + 2 * d * (d + 1) * (2 * d + 1) / 3 - d * (d + 1);
    s %= modulo;
    if (x == y)
        return s;
    else if (x > y)
    {
        int s2 = (x - y) * y * (-y - 1) + 2 * y * x * (x + 1) - 2 * y * y * (y + 1);
        s += s2;
        s %= modulo;
        return s;
    }
    else
    {
        int s2 = x * (y - x) * (x + 1);
        s += s2;
        s %= modulo;
        return s;
    }
}

int stanga_jos(int x,int y)///atentie la semne!!
{
    ///de la -x la -1 si de la -y la -1
    int d = min(x,y);
    if (d <= 0)
        return 0;
    int s = dreapta_sus(x,y) + 4 * d * (d + 1) * (2 * d + 1) / 3 - 2 * d * (d + 1);
    if (x == y)
        return s;
    else if (x > y)
    {
        int s2 = 2 * y * x * (x + 1) - 2 * y * y * (y + 1);
        s += s2;
        //cout << (ll)s2 << endl;
        s %= modulo;
        return s;
    }
    else
    {
        int s2 = 2 * x * y * (y + 1) - 2 * x * x * (x + 1);
        s += s2;
        s %= modulo;
        return s;
    }
}

int dreapta_jos(int x,int y)
{
    ///de la 1 la x si de la -1 la -y
    int d = min(x,y);
    if (d <= 0)
        return 0;
    int s = 2 * d * d * (d - 1) * (d - 1) + 4 * (d - 1) * d * (2 * d - 1) / 3 + d * (d - 1) + d * (2 * d + 1) * (2 * d + 1);
    //cout << (ll)s << endl;
    s %= modulo;
    if (x == y)
        return s;
    else if (x > y)
    {
        int s2 = -(x - y) * y * y + (x - y) * y * x * (x + 1) / 2 - (x - y) * y * y * (y + 1) / 2 + (x - y) * y * (y - 1) / 2 + (x - y) * y - 2 * y * x * (x + 1) + 2 * y * y * (y + 1) + 2 * y * x * (x + 1) * (2 * x + 1) / 3 - 2 * y * y * (y + 1) * (2 * y + 1) / 3;
        s += s2;
        s %= modulo;
        return s;
    }
    else
    {
        int s2 = -(y - x) * x * (x - 1) / 2 + (y - x) * x * x - x * y * (y + 1) / 2 + x * x * (x + 1) / 2 + (y - x) * x + 2 * x * y * (y + 1) - 2 * x * x * (x + 1) + 2 * x * y * (y + 1) * (2 * y + 1) / 3 - 2 * x * x * (x + 1) * (2 * x + 1) / 3;
        s += s2;
        s %= modulo;
        return s;
    }
}

int dreapta(int x)
{
    ///de la 1 la x, cu y = 0
    int s = x * (x + 1) / 2 + x - 2 * x * (x + 1) + 2 * x * (x + 1) * (2 * x + 1) / 3;
    s %= modulo;
    return s;
}

int stanga(int x)
{
    ///de la -x la -1, cu y = 0
    int s = dreapta(x) + 2 * x * (x + 1);
    s %= modulo;
    return s;
}

int sus(int y)
{
    ///de la 1 la y, cu x = 0
    int s = dreapta(y) + y * (y + 1);
    s %= modulo;
    return s;
}

int jos(int y)
{
    ///de la -y la -1, cu x = 0
    int s = dreapta(y) + 3 * y * (y + 1);
    s %= modulo;
    return s;
}

void testcase()
{
    ll X1,Y1,X2,Y2;
    cin >> X1 >> Y1 >> X2 >> Y2;
    int x1 = X1,x2 = X2,y1 = Y1,y2 = Y2;
    int ans = 0;
    if (x1 <= 0 and x2 >= 0 and y1 <= 0 and y2 >= 0)
        ans = 1;
    if (x1 <= 0 and x2 >= 0)
    {
        if (y1 > 0)
            ans += sus(y2) - sus(y1 - 1);
        else if (y2 < 0)
            ans += jos(-y1) - jos(-y2 - 1);
        else
            ans += sus(y2) + jos(-y1);
    }
    if (y1 <= 0 and y2 >= 0)
    {
        if (x1 > 0)
            ans += dreapta(x2) - dreapta(x1 - 1);
        else if (x2 < 0)
            ans += stanga(-x1) - stanga(-x2 - 1);
        else
            ans += dreapta(x2) + stanga(-x1);
    }
    //cout << (ll)ans << endl;
    int gx1,gx2,gy1,gy2;
    gx1 = max(1ll,(ll)x1);
    gx2 = x2;
    gy1 = max(1ll,(ll)y1);
    gy2 = y2;
    if (gx2 >= gx1 and gy2 >= gy1)
    {
        ans += dreapta_sus(gx2,gy2) + dreapta_sus(gx1 - 1,gy1 - 1) - dreapta_sus(gx2,gy1 - 1) - dreapta_sus(gx1 - 1,gy2);
    }
    //cout << (ll)ans << endl;
    gx1 = x1;
    gx2 = min((ll)x2,-1ll);
    if (gx2 >= gx1 and gy2 >= gy1)
    {
        ans += stanga_sus(-gx1,gy2) + stanga_sus(-gx2 - 1,gy1 - 1) - stanga_sus(-gx1,gy1 - 1) - stanga_sus(-gx2 - 1,gy2);
        ///(3,3) - (3,1)
    }
    //cout << (ll)stanga_sus(3,3) << ' ' << (ll)stanga_sus(3,1) << endl;
    //cout << (ll)ans << endl;
    gy1 = y1;
    gy2 = min((ll)y2,-1ll);
    if (gx2 >= gx1 and gy2 >= gy1)
    {
        ans += stanga_jos(-gx1,-gy1) + stanga_jos(-gx2 - 1,-gy2 - 1) - stanga_jos(-gx1,-gy2 - 1) - stanga_jos(-gx2 - 1,-gy1);
    }
    //cout << (ll)ans << endl;
    gx1 = max(1ll,(ll)x1);
    gx2 = x2;
    if (gx2 >= gx1 and gy2 >= gy1)
    {
        ans += dreapta_jos(gx2,-gy1) + dreapta_jos(gx1 - 1,-gy2 - 1) - dreapta_jos(gx2,-gy2 - 1) - dreapta_jos(gx1 - 1,-gy1);
    }
    //cout << (ll)ans << endl;
    ans += modulo * modulo;
    ans %= modulo;
    ans += modulo;
    ans %= modulo;
    cout << (ll)ans << '\n';
}

signed main()
{
    ll n,tc;
    cin >> n >> tc;
    while (tc--)
        testcase();
    return 0;
}

///-3 2 2 3

/**
cea mai de mate de a 5a problema
**/

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