oj.uz

Submission #32268

# Submission time Handle Problem Language Result Execution time Memory
32268 2017-10-06T00:51:44 Z dqhungdl Spiral (BOI16_spiral) C++14
15 / 100
 1500 ms 33580 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int n,T;
int64_t a[2005][2005];

void Sub1()
{
    a[n+1][n+1]=1;
    int ii=1,jj=0,Count=1;
    for(int i=1;i<=n;i++)
    {
        while(jj<=i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            jj++;
        }
        jj--;
        ii--;
        while(ii>=-i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            ii--;
        }
        ii++;
        jj--;
        while(jj>=-i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            jj--;
        }
        jj++;
        ii++;
        while(ii<=i)
        {
            a[ii+n+1][jj+n+1]=++Count;
            ii++;
        }
    }
    for(int i=1;i<=2*n+1;i++)
        for(int j=1;j<=2*n+1;j++)
            a[i][j]=(a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1]+mod)%mod;
    int u1,v1,u2,v2;
    while(T--)
    {
        cin>>u1>>v1>>u2>>v2;
        u1+=n+1;
        v1+=n+1;
        u2+=n+1;
        v2+=n+1;
        cout<<(a[u2][v2]-a[u1-1][v2]-a[u2][v1-1]+a[u1-1][v1-1]+2*mod)%mod<<"\n";
    }
}

void Sub2(int u,int v)
{
    int64_t Class=max(abs(u)-1,abs(v)-1);
    int64_t Count=(2*Class+1)*(2*Class+1)+1;
    int i=Class+1,j=-Class;
    if(u==i&&v>=j)
    {
        cout<<(Count+v-j)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=Class,j=Class+1;
    if(u<=i&&v==j)
    {
        cout<<(Count+i-u)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=-Class-1,j=Class;
    if(u==i&&v<=j)
    {
        cout<<(Count+j-v)%mod<<"\n";
        return;
    }
    Count+=2*Class+2;
    i=-Class,j=-Class-1;
    if(u>=i&&v==j)
    {
        cout<<(Count+u-i)%mod<<"\n";
        return;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("SPIRAL.INP","r",stdin);
    cin>>n>>T;
    if(n<=1000)
        Sub1();
    int u1,v1,u2,v2;
    while(T--)
    {
        cin>>u1>>v1>>u2>>v2;
        if(u1==u2&&v1==v2)
            Sub2(u1,v1);
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1500 ms 33580 KB Execution timed out

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1500 ms 33580 KB Execution timed out

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 33580 KB Output isn't correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1500 ms 33580 KB Execution timed out