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:01:47100
2016-05-12 12:49:390
2016-05-12 11:57:4658
2016-05-12 11:56:5727
2016-05-12 11:46:2327
2016-05-12 11:45:1827
2016-05-12 11:44:1815
2016-05-12 11:05:5915
2016-05-12 09:58:3515
Task:Spiral
Sender:phobos
Submission time:2016-05-12 11:45:18
Language:C++
Status:READY
Score:27

Feedback

groupverdictscore
#1ACCEPTED12
#2ACCEPTED15
#3WRONG ANSWER0
#4WRONG ANSWER0
#5WRONG ANSWER0

Test results

testverdicttime (s)group
#1ACCEPTED0.42 / 1.501details
#2ACCEPTED0.06 / 1.502details
#3WRONG ANSWER0.05 / 1.503details
#4WRONG ANSWER0.05 / 1.504details
#5WRONG ANSWER0.06 / 1.505details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:69:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &q);
                           ^
input/code.cpp:72:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
                                                ^
input/code.cpp: In function 'long long int get(long long int, long long int)':
input/code.cpp:34:9: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ret;
         ^

Code

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iostream>
#define ll long long
using namespace std;
ll n, q;
const ll MOD = 1e9+7;

ll get(ll x, ll y) {
	ll ret;
	if (x == y && y == 0) ret = 1;
	else if (fabs(x) == fabs(y)) {
		ll m = fabs(x);
		if (x > 0 && y > 0) ret = ((2*m-1)*(2*m-1)+2*m)%MOD;
		if (x < 0 && y > 0) ret = ((2*m-1)*(2*m-1)+4*m)%MOD;
		if (x < 0 && y < 0) ret = ((2*m-1)*(2*m-1)+6*m)%MOD;
		if (x > 0 && y < 0) ret = ((2*m-1)*(2*m-1)+8*m)%MOD;
	}
	else {
		if (fabs(x) > fabs(y)) {
			ll m = fabs(x);
			if (x > 0) ret = ((2*m-1)*(2*m-1)+m+y)%MOD;
			else ret = ((2*m-1)*(2*m-1)+5*m-y)%MOD;
		}
		else {
			ll m = fabs(y);
			if (y > 0) ret = ((2*m-1)*(2*m-1)+3*m-x)%MOD;
			else ret = ((2*m-1)*(2*m-1)+7*m+x)%MOD;
		}
	}
	return ret;
}

ll sumsq(ll a, ll b) {
	a--;
	ll p = (a*(a+1))%MOD; p = (p*(2*a+1))%MOD; if (p%2) {p += MOD;}; p /= 2; while (p%3) {p += MOD;}; p /= 3;
	ll q = (b*(b+1))%MOD; q = (q*(2*b+1))%MOD; if (q%2) {q += MOD;}; q /= 2; while (q%3) {q += MOD;}; q /= 3;
	return (q-p+MOD)%MOD;
}

ll sum(ll a, ll b) {
	a--;
	ll p = (a*(a+1)/2)%MOD; ll q = (b*(b+1)/2)%MOD;
	return (q-p+MOD)%MOD;
}

ll solve(ll x, ll y) {
	if (x < 0 || y < 0) return 0;
	ll ret = 1, k = min(x, y);
	ll add = (k*k)%MOD; add = (add*(k+1))%MOD; add = (add*(k+1))%MOD; add = (add*2)%MOD; add = (add+k)%MOD;
	ret = (ret+add)%MOD;
	if (x > y) {
		ll a1 = (4*sumsq(y+1, x))%MOD; a1 = ((a1-4*sum(y+1, x))%MOD+MOD)%MOD; a1 = (a1+x-y)%MOD; a1 = (a1*(y+1))%MOD;
		ll a2 = (2*sum(y+1, x))%MOD; a2 = (a2+y*(x-y))%MOD; a2 = (a2*(y+1))%MOD; if (a2%2) {a2 += MOD;}; a2 /= 2;
		ret = (ret+a1+a2)%MOD;
	}
	else if (y > x) {
		ll a1 = (4*sumsq(x+1, y))%MOD; a1 = ((a1-4*sum(x+1, y))%MOD+MOD)%MOD; a1 = (a1+y-x)%MOD; a1 = (a1*(x+1))%MOD;
		ll a2 = (6*sum(x+1, y))%MOD; a2 = ((a2-x*(y-x))%MOD+MOD)%MOD; a2 = (a2*(x+1))%MOD; if (a2%2) {a2 += MOD;}; a2 /= 2;
		ret = (ret+a1+a2)%MOD;
	}
	return ret;
}

int main() {
	scanf("%lld%lld", &n, &q);
	for (int i = 0; i < q; i++) {
		ll x1, y1, x2, y2;
		scanf("%lld%lld%lld%lld", &x1, &y1, &x2, &y2);
		if (x1 == x2 && y1 == y2) printf("%lld\n", get(x1, y1));
		else if (n <= 1000) {
			ll ans = 0;
			for (int i = x1; i <= x2; i++) for (int j = y1; j <= y2; j++) {
				ans = (ans+get(i, j))%MOD;
			}
			printf("%lld\n", ans);
		}
		else {
			ll ans = (solve(x2, y2)-solve(x1-1, y2)-solve(x2, y1-1)+solve(x1-1, y1-1))%MOD;
			printf("%lld\n", ans);
		}
	}
	return 0;
}

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: WRONG ANSWER

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
0
826975265
0
18263594
-84610937
...
view   save

Test 4

Group: 4

Verdict: WRONG ANSWER

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
-304038849
-42639831
137575768
-477767867
58884045
...
view   save

Test 5

Group: 5

Verdict: WRONG ANSWER

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

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

user output
0
0
239483569
113507818
-721597059
...
view   save