Code Submission Evaluation System Login

BOI 2016, day 1

Start:2016-05-12 09:00:00
End:2016-05-12 14:00:00
 

Tasks | Scoreboard | Statistics


CSES - BOI 2016, day 1 - Results
History
2016-05-12 13:59:5227
2016-05-12 13:58:4415
2016-05-12 13:56:090
2016-05-12 13:55:140
2016-05-12 13:49:1512
2016-05-12 13:47:170
2016-05-12 13:07:5227
Task:Spiral
Sender:whitewind664
Submission time:2016-05-12 13:59:52
Language:C++
Status:READY
Score:27

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3TIME LIMIT EXCEEDED0
#4TIME LIMIT EXCEEDED0
#5TIME LIMIT EXCEEDED0

Test results

testverdicttime (s)group
#1ACCEPTED0.06 / 1.501details
#2ACCEPTED0.05 / 1.502details
#3TIME LIMIT EXCEEDED-- / 1.503details
#4TIME LIMIT EXCEEDED-- / 1.504details
#5TIME LIMIT EXCEEDED-- / 1.505details

Code

#include <iostream>
#include <vector>
#include <cstdlib>
#include <queue>
#include <math.h>
#define f first
#define s second

using namespace std;

long long presmeti(long long j, long long k)
{
    long long br=(((2*max(abs(k), abs(j))+1)%1000000007)*((2*max(abs(k), abs(j))+1)%1000000007))%1000000007;
    if (j==max(abs(k), abs(j)) && j!=-k)
    {
        br-=(j-k)%1000000007;
        br=(br%1000000007+1000000007)%1000000007;
        k=max(abs(k), abs(j));
    }
    if (k==max(abs(k), abs(j)))
    {
        br-=(k+j)%1000000007;
        br=(br%1000000007+1000000007)%1000000007;
        j=-max(abs(k), abs(j));
    }
    if (j==-max(abs(k), abs(j)))
    {
        br-=(-j+k)%1000000007;
        br=(br%1000000007+1000000007)%1000000007;
        k=-max(abs(k), abs(j));
    }
    if (k==-max(abs(k), abs(j)))
    {
        br-=(-k-j)%1000000007;
        br=(br%1000000007+1000000007)%1000000007;
    }
    return br;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    if (n>=1000 && n<=100000)
    {
        for (int i=0; i<q; i++)
        {
            long long x1, x2, y1, y2, br=0;
            cin >> x1 >> y1 >> x2 >> y2;
            while (x1!=x2 && y1!=y2)
            {
                long long a, b, c, d;
                a=presmeti(x1, y1);
                b=presmeti(x1, y2);
                c=presmeti(x2, y1);
                d=presmeti(x2, y2);
                if (abs(b-a)==y2-y1)
                {
                    if ((a+b)%2==0)
                    {
                        br+=((((a+b)/2)%1000000007)*((max(a, b)-min(a, b)+1)%1000000007))%1000000007;
                    }
                    else
                    {
                        br+=(((a+b)%1000000007)*(((max(a, b)-min(a, b)+1)/2)%1000000007))%1000000007;
                    }
                    br%=1000000007;
                    x1++;
                }
                else if (abs(c-a)==x2-x1)
                {
                    if ((a+c)%2==0)
                    {
                        br+=((((a+c)/2)%1000000007)*((max(a, c)-min(a, c)+1)%1000000007))%1000000007;
                    }
                    else
                    {
                        br+=(((a+c)%1000000007)*(((max(a, c)-min(a, c)+1)/2)%1000000007))%1000000007;
                    }
                    br%=1000000007;
                    y1++;
                }
                else if (abs(b-d)==x2-x1)
                {
                    if ((d+b)%2==0)
                    {
                        br+=((((d+b)/2)%1000000007)*((max(d, b)-min(d, b)+1)%1000000007))%1000000007;
                    }
                    else
                    {
                        br+=(((d+b)%1000000007)*(((max(d, b)-min(d, b)+1)/2)%1000000007))%1000000007;
                    }
                    br%=1000000007;
                    y2--;
                }
                else
                {
                    if ((c+d)%2==0)
                    {
                        br+=((((c+d)/2)%1000000007)*((max(c, d)-min(c, d)+1)%1000000007))%1000000007;
                    }
                    else
                    {
                        br+=(((d+c)%1000000007)*(((max(d, c)-min(d, c)+1)/2)%1000000007))%1000000007;
                    }
                    br%=1000000007;
                    x2--;
                }
            }
            if (x1==x2)
            {
                for (int j=y1; j<=y2; j++)
                {
                    br+=presmeti(x1, j)%1000000007;
                    br%=1000000007;
                }
            }
            else if (y1==y2)
            {
                for (int j=x1; j<=x2; j++)
                {
                    br+=presmeti(j, y1)%1000000007;
                    br%=1000000007;
                }
            }
            cout << br << endl;
        }
        return 0;
    }
    for (int i=0; i<q; i++)
    {
        long long x1, x2, y1, y2, br=0;
        cin >> x1 >> y1 >> x2 >> y2;
        for (long long p=x1; p<=x2; p++)
        {
            for (long long q=y1; q<=y2; q++)
            {
//                br+=presmeti(p, q);
//                br%=1000000007;
                long long j=p, k=q;
                br+=(((2*max(abs(k), abs(j))+1)%1000000007)*((2*max(abs(k), abs(j))+1)%1000000007))%1000000007;
                if (j==max(abs(k), abs(j)) && j!=-k)
                {
                    br-=(j-k)%1000000007;
                    br=(br%1000000007+1000000007)%1000000007;
                    k=max(abs(k), abs(j));
                }
                if (k==max(abs(k), abs(j)))
                {
                    br-=(k+j)%1000000007;
                    br=(br%1000000007+1000000007)%1000000007;
                    j=-max(abs(k), abs(j));
                }
                if (j==-max(abs(k), abs(j)))
                {
                    br-=(-j+k)%1000000007;
                    br=(br%1000000007+1000000007)%1000000007;
                    k=-max(abs(k), abs(j));
                }
                if (k==-max(abs(k), abs(j)))
                {
                    br-=(-k-j)%1000000007;
                    br=(br%1000000007+1000000007)%1000000007;
                }
            }
        }
        cout << br << endl;
    }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
1000 100
-709 0 1000 123
-621 -1000 -102 -435
-602 -560 276 -356
-945 -590 0 -468
...
view   save

correct output
788057008
633127082
507903329
53165899
558016315
...
view   save

user output
788057008
633127082
507903329
53165899
558016315
...
view   save

Test 2

Group: 2

Verdict: ACCEPTED

input
1000000000 100
181053719 1000000000 181053719...
view   save

correct output
818946492
750635163
193830026
660632411
46072376
...
view   save

user output
818946492
750635163
193830026
660632411
46072376
...
view   save

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
100000 100
-88233 -87279 -49871 52277
-86645 -7997 48948 30702
-79916 -36210 -21257 -16821
0 57331 93163 100000
...
view   save

correct output
986592951
708386765
85336595
18263594
32233727
...
view   save

user output
(empty)

Test 4

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
1000000000 100
1 1 21134200 719983102
1 1 929463279 1000000000
1 1 68450838 1
1 1 84417340 297177199
...
view   save

correct output
695961158
957360176
137575768
522232140
58884045
...
view   save

user output
(empty)

Test 5

Group: 5

Verdict: TIME LIMIT EXCEEDED

input
1000000000 100
-857489445 -1000000000 -432836...
view   save

correct output
902627632
581519884
819269364
857298983
278402948
...
view   save

user output
(empty)