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 10:24:4944
Task:Spiral
Sender:ulrikdem
Submission time:2016-05-12 10:24:49
Language:C++
Status:READY
Score:44

Feedback

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

Test results

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

Code

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	while(q--) {
		long long x1, y1, x2, y2, sum = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		for(long long x = x1; x <= x2; ++x) {
			long long start, end = (2 * abs(x) + 1) * (2 * abs(x) + 1);
			if(x < 0) {
				if(y2 < x || y1 >= -x) {
					continue;
				}
				end -= abs(x) * 2 + (max(y1, x) - x);
				start = end - (min(y2, -x - 1) - max(y1, x));
			} else if(x > 0) {
				if(y1 > x || y2 <= -x) {
					continue;
				}
				end -= abs(x) * 6 + (x - min(y2, x));
				start = end - (min(y2, x) - max(y1, -x + 1));
			} else {
				if(y1 > 0 || y2 < 0) {
					continue;
				}
				start = 1;
			}
			sum += (start - 1) % mod * (end - start + 1);
			sum += (end - start + 1) * (end - start + 2) / 2;
			sum %= mod;
		}
		for(long long y = y1; y <= y2; ++y) {
			long long start, end = (2 * abs(y) + 1) * (2 * abs(y) + 1);
			if(y < 0) {
				if(x1 > -y || x2 <= y) {
					continue;
				}
				end -= abs(y) * 0 + (-y - min(x2, -y));
				start = end - (min(x2, -y) - max(x1, y + 1));
			} else if(y > 0) {
				if(x2 < -y || x1 >= y) {
					continue;
				}
				end -= abs(y) * 4 + (y + max(x1, -y));
				start = end - (min(x2, y - 1) - max(x1, -y));
			} else {
				continue;
			}
			sum += (start - 1) % mod * (end - start + 1);
			sum += (end - start + 1) * (end - start + 2) / 2;
			sum %= mod;
		}
		cout << sum << '\n';
	}
	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: ACCEPTED

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
986592951
708386765
85336595
18263594
32233727
...
view   save

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)