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:57:4827
2016-05-12 13:53:5127
2016-05-12 13:49:560
2016-05-12 13:44:4812
2016-05-12 13:35:590
2016-05-12 13:26:360
2016-05-12 13:12:380
2016-05-12 13:10:410
2016-05-12 13:04:140
2016-05-12 12:58:280
2016-05-12 12:57:190
2016-05-12 12:54:590
2016-05-12 12:54:24
2016-05-12 12:35:580
2016-05-12 12:35:050
2016-05-12 12:32:350
Task:Spiral
Sender:jDomantas
Submission time:2016-05-12 13:57:48
Language:C++
Status:READY
Score:27

Feedback

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

Test results

testverdicttime (s)group
#1ACCEPTED0.10 / 1.501details
#2ACCEPTED0.10 / 1.502details
#3WRONG ANSWER0.09 / 1.503details
#4WRONG ANSWER0.12 / 1.504details
#5WRONG ANSWER0.09 / 1.505details

Compiler report

input/code.cpp:1:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker, "/stack:20000000")
 ^

Code

#pragma comment(linker, "/stack:20000000")
#define _CRT_SECURE_NO_DEPRECATE
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <limits.h>
#include <algorithm>
#include <iomanip>
#include <string>
#include <string.h>
#include <math.h>
#include <fstream>
using namespace std;
/**/
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<pll, ll> plll;
typedef pair<double, double> pdd;

#define fst first
#define snd second

#define mp(a, b) make_pair((a), (b))
#define pp push_back
#define PI 3.1415926535897.9323846264338327

#define fori(n) for(int i = 0; i < (n); ++i)
#define forj(n) for(int j = 0; j < (n); ++j)
#define forir(n) for(int i = (n) - 1; i >= 0; --i)
#define forjr(n) for(int j = (n) - 1; j >= 0; --j)

void redirectIO() {
#if defined(_DEBUG) || defined(_RELEASE)
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

#define mod (ll)((ll)1e9 + (ll)7)

#if defined(_DEBUG) || defined(_RELEASE)
#define maxn 2000
#else
#define maxn 2000
#endif

ll sums[2100][2100];

ll single(ll x, ll y) {
	ll d = max(abs(x), abs(y)) + 1;
	ll g = ((4 * d) % mod * d) % mod;
	g = (g + 11 * (mod - d)) % mod;
	g = (g + 8) % mod;
	if (x >= 0 && abs(x) > abs(y)) {
		return (g + y + mod) % mod;
	} 
	if (y >= 0 && abs(x) <= abs(y)) {
		g = (g + 2 * d - 2) % mod;
		return (g - x + mod) % mod;
	}
	if (x <= 0 && abs(x) > abs(y)) {
		g = (g + 2 * d - 2) % mod;
		g = (g + 2 * d - 2) % mod;
		return (g - y + mod) % mod;
	}
	g = (g + 2 * d - 2) % mod;
	g = (g + 2 * d - 2) % mod;
	g = (g + 2 * d - 2) % mod;
	return (g + x + mod) % mod;
}

void init() {
	fori(2100) forj(2100) sums[i][j] = 0;
	int x = 1050;
	int y = 1050;
	int val = 2;
	int s = 1;
	sums[x][y] = 1;
	while (x >= 5 && y >= 5 && x < 2095 && y < 2095) {
		fori(s) {
			x++;
			sums[x][y] = val++;
		}
		fori(s) {
			y++;
			sums[x][y] = val++;
		}
		s++;
		fori(s) {
			x--;
			sums[x][y] = val++;
		}
		fori(s) {
			y--;
			sums[x][y] = val++;
		}
		s++;
	}

	for (int x = 0; x < 2100; x++)
		for (int y = 0; y < 2100; y++) {
			ll a = x == 0 ? 0 : sums[x - 1][y];
			ll b = y == 0 ? 0 : sums[x][y - 1];
			ll c = (x == 0 || y == 0) ? 0 : sums[x - 1][y - 1];
			sums[x][y] = (sums[x][y] - c + a + b + mod * (ll)4) % mod;
		}
}

ll sum(int x, int y) {
	x += 1050;
	y += 1050;
	return sums[x][y];
}

void check() {
	for (int x = -990; x <= 990; x++)
		for (int y = -990; y <= 990; y++) {
			ll t = sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
			t = (t + 4 * mod) % mod;
			if (t != single(x, y)) {
				cout << x << " " << y << endl;
				cout << t << endl;
				cout << single(x, y) << endl;
				return;
			}
		}
}

ll gs(ll n) {
	ll r = (n * (n + 1)) % mod;
	r = (r * (((ll)2 * n + (ll)1) % mod)) % mod;
	r = ((((ll)2 * r) % mod) * (ll)333333336) % mod;

	ll a = ((n * (n + 1)) / 2) % mod;
	a = (11 * a) % mod;

	r = (r + mod - a) % mod;
	r = (r + (8 * n) % mod) % mod;

	return r;
}

ll gs2(ll n) {
	ll r = gs(n);
	r = (r + n * (n - 1)) % mod;
	return r;
}

// square (0; 0) (n; n)
ll psquare(ll n) {
	n++;

	ll r = (2 * n * n) % mod;
	r = (r * (n + 1)) % mod;
	r = (r * (n + 1)) % mod;

	ll a = (((4 * n) % mod) * (n + 1)) % mod;
	a = (a * ((2 * n + 1) % mod)) % mod;

	ll c = (12 * n * (n + 1)) % mod;
	ll d = (7 * n) % mod;

	r = (r + mod - a) % mod;
	r = (r + mod + c) % mod;
	r = (r + mod - d) % mod;

	return r;
}

// x >= y >= 0
ll prect1(ll x, ll y) {
	x++;
	y++;
	ll g = (gs(x) + mod - gs(y)) % mod;
	ll v = (y * (y - 1) / 2) % mod;
	g = ((g * y) % mod + v * (x - y) % mod) % mod;
	return (g + psquare(y - 1)) % mod;
}

//  y >= x >= 0
ll prect2(ll x, ll y) {
	x++;
	y++;
	ll g = (gs2(y) + mod - gs2(x)) % mod;
	ll v = (x * (x - 1) / 2) % mod;
	g = ((g * x) % mod + mod - v * (y - x) % mod) % mod;
	return (g + psquare(x - 1)) % mod;
}

// rectangle (0; 0) (x; y)
// x, y >= 0
ll prect(ll x, ll y) {
	if (x < 0 || y < 0) return 0;
	if (x >= y)
		return prect1(x, y);
	else
		return prect2(x, y);
}

ll p(ll x, ll y) {
	return (prect(x, y) - prect(x, 0) - prect(0, y) + 1 + 4 * mod) % mod;
}

int main()
{
	redirectIO();

	/*init();
	check();*/

	ll n, q;
	cin >> n >> q;
	//if (n > 1000) return 0;
	init();
	//check();
	int x1, y1, x2, y2;
	while (q--) {
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2 && y1 == y2 && n > 1000) {
			cout << single(x1, y1) << endl;
			continue;
		}
		if (x1 == 1 && y1 == 1 && n > 1000) {
			cout << p(x2, y2) << endl;
			continue;
		}
		if (n > 1000) return 0;
		ll a = sum(x2, y2);
		ll b = sum(x1 - 1, y2);
		ll c = sum(x2, y1 - 1);
		ll d = sum(x1 - 1, y1 - 1);
		if (a < 0 || b < 0 || c < 0 || d < 0 || a >= mod || b >= mod || c >= mod || d >= mod)
			return 1;
		ll res = a - b - c + d + (ll)2 * (ll)mod;
		if (res < 0)
			return 1;
		res %= mod;
		cout << res << endl;
	}

	/*for (int y = 7; y >= 0; y--) {
		for (int x = 0; x <= 7; x++) {
			ll c = single(x, y);// sum(x, y) - sum(x - 1, y) - sum(x, y - 1) + sum(x - 1, y - 1);
			cout << ((c + 3 * mod) % mod) << "\t";
		}
		cout << endl;
	}*/

	return 0;
}

// Park (B)

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
(empty)

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
695961158
375016168
137575768
522232140
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
(empty)