Submission #1277396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277396		behesht	Spiral (BOI16_spiral)	C++20	100 / 100	1 ms	572 KiB

spiral

#include <bits/stdc++.h>
 
#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1
 
using namespace std;
 
const int INF = 1e9 + 24 + (34 / 10); // 34 ---> 35
const int MAXN = 2e5 + 24 + (34 / 10); // 34 ---> 35
const int MOD = 1e9 + 7;
 
int pw(int a, int b){
 
	if(b == 0)
		return 1;
 
	int res = pw(a, b / 2);
	res = (res * res) % MOD;
 
	if(b & 1)
		res = (res * a) % MOD;
	
	return res;
}
 
int T1(int x, int y){
 
	int res = y * (y + 1) / 2 % MOD;
	res %= MOD;
 
	if(x != 1)
		res -= T1(1, x - 1);
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	return res;
}
 
int T2(int x, int y){
 
	int res = y * (y + 1) % MOD;
	res *= (2 * y + 1) % MOD * pw(6, MOD - 2) % MOD;
	
	if(x != 1)
		res -= T2(1, x - 1);
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	return res;
}	
 
int T3(int x, int y){
 
	int res = y * (y + 1) / 2 % MOD;
	res %= MOD;
	res *= res;
	res %= MOD;
 
	if(x != 1)
		res -= T3(1, x - 1);
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	return res;
}
 
int Hal1(int x1, int y1, int x2, int y2){
 
	if(x1 > 1 || y1 > 1){
		int ans = Hal1(1, 1, x2, y2);
 
		if(x1 > 1)
			ans -= Hal1(1, 1, x1 - 1, y2), ans %= MOD;
 
		if(y1 > 1)
			ans -= Hal1(1, 1, x2, y1 - 1), ans %= MOD;
 
		if(x1 > 1 && y1 > 1)
			ans += Hal1(1, 1, x1 - 1, y1 - 1), ans %= MOD;
 
		return ans % MOD;
	}
 
	int X = min(x2, y2);
	int res = 0;
 
	// satrrr
	if(y2 > x2){
 
		int x = x2 + 1, y = y2;
		int n = x2, m = y - x + 1;
		
		// d4(x, y, n, m);
		res -= n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
		res += n * 4 * T2(x, y) % MOD;
		res %= MOD;
		res -= n * T1(x, y);
		res %= MOD;
	}
 
	// sotoooon
	else if(y2 < x2){
		
		int x = y2 + 1, y = x2;
		int n = y2, m = y - x + 1;
 
		res += n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res -= 3 * n * T1(x, y) % MOD;
		res %= MOD;
		res += 2 * n * m % MOD;
		res %= MOD;
	}
 
	res -= X % MOD;
	res %= MOD;
	res += 8 * T3(1, X) % MOD;
	res %= MOD;
	res -= 8 * T2(1, X) % MOD;
	res %= MOD;
	res += 4 * T1(1, X) % MOD;
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	// d2(1, res);
	return res;
}
 
int Hal2(int x1, int y1, int x2, int y2){
	
	if(x1 < 0 || y1 > 1){
 
		int ans = Hal2(0, 1, x2, y2);
 
		if(x1 < 0)
			ans -= Hal2(0, 1, -x1 - 1, y2), ans %= MOD;;
 
		if(y1 > 1)
			ans -= Hal2(0, 1, x2, y1 - 1), ans %= MOD;;
 
		if(x1 < 0 && y1 > 1)
			ans += Hal2(0, 1, -x1 - 1, y1 - 1), ans %= MOD;;
 
		return ans % MOD;
	}
 
	int X = min(x2, y2);
	int res = 0;
 
	// satrrrrr
	if(x2 < y2){
		int x = x2 + 1, y = y2;
		int n = x2 + 1, m = y - x + 1;
		
		res += n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
		res += m * n % MOD;
		res %= MOD;
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res -= n * T1(x, y);
		res %= MOD;
	}
 
	else if(x2 > y2){
		int x = y2 + 1, y = x2;
		int n = y2, m = y - x + 1;
 
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res += n * T1(x, y) % MOD;
		res %= MOD;
		res -= n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
	}
 
	res += 8 * T3(1, X) % MOD;
	res %= MOD;
	res += T1(1, X);
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	// d2(2, res);
	return res;
}
 
int Hal3(int x1, int y1, int x2, int y2){
 
	// d4(x1, y1, x2, y2);
	if(x1 < 0 || y1 < 0){
 
		int ans = Hal3(0, 0, x2, y2);
 
		if(x1 < 0){
			// d1(1111111);
			ans -= Hal3(0, 0, -x1 - 1, y2);
			ans %= MOD;
		}
 
		if(y1 < 0){
			// d1(2);
			ans -= Hal3(0, 0, x2, -y1 - 1);
			ans %= MOD;
		}
 
		if(x1 < 0 && y1 < 0){
			// d1(3);
			ans += Hal3(0, 0, -x1 - 1, -y1 - 1);
			ans %= MOD;
		}
 
		return ans % MOD;
	}
 
	int X = min(x2, y2);
	int res = 1;
 
	if(x2 < y2){
		int x = x2 + 1, y = y2;
		int n = x2 + 1, m = y - x + 1;
 
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res += 3 * n * T1(x, y) % MOD;
		res %= MOD;
		res += n * m % MOD;
		res %= MOD;
		res -= n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
	}
 
	else if(x2 > y2){
		int x = y2 + 1, y = x2;
		int n = y2 + 1, m = y - x + 1;
 
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res += n * T1(x, y) % MOD;
		res %= MOD;
		res += n * m % MOD;
		res %= MOD;
		res += n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
	}
 
	res += X;
	res %= MOD;
	res += 8 * T3(1, X) % MOD;
	res %= MOD;
	res += 8 * T2(1, X) % MOD;
	res %= MOD;
	res += 4 * T1(1, X) % MOD;
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	// d2(3, res);
 
	return res;
}
 
int Hal4(int x1, int y1, int x2, int y2){
 
	// d4(x1, y1, x2, y2);
 
	if(x1 > 1 || y1 < 0){
 
		int ans = Hal4(0, 1, x2, y2);
 
		if(x1 > 1)
			ans -= Hal4(0, 1, x1 - 1, y2), ans %= MOD;
 
		if(y1 < 0)
			ans -= Hal4(0, 1, x2, -y1 - 1), ans %= MOD;
 
		if(x1 > 1 && y1 < 0)
			ans += Hal4(0, 1, x1 - 1, -y1 - 1), ans %= MOD;
 
		return ans % MOD;
	}
 
	int X = min(x2 - 1, y2);
	int res = 2;
 
	// satrrrr
	if(x2 < y2 + 1){
		int x = x2, y = y2;
		int n = x2, m = y - x + 1;
 
		// d4(x, y, n, m);
 
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res += 3 * n * T1(x, y) % MOD;
		res %= MOD;
		res += 2 * n * m % MOD;
		res %= MOD;
		res += n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
		// d1(res);
	}
 
	else if(x2 > y2 + 1){
		int x = y2 + 2, y = x2;
		int n = y2 + 1, m = y - x + 1;
 
		res += 4 * n * T2(x, y) % MOD;
		res %= MOD;
		res -= 3 * n * T1(x, y) % MOD;
		res %= MOD;
		res += n * m % MOD;
		res %= MOD;
		res -= n * (n - 1) / 2 % MOD * m % MOD;
		res %= MOD;
	}
	
	if(X > 0){
		res += X * 2;
		res %= MOD;
		res += 8 * T3(1, X) % MOD;
		res %= MOD;
		res += 12 * T2(1, X) % MOD;
		res %= MOD;
		res += 8 * T1(1, X) % MOD;
		res %= MOD;
	}
 
	res %= MOD;
	res += MOD;
	res %= MOD;
 
	// d4(x1, y1, x2, y2);
	// d2(4, res);
 
	return res;
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
	int n, q;
	cin >> n >> q;
	
	while(q--){
 
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
 
		int ans = 0;
		int X1 = abs(x1);
		int Y1 = abs(y1);
		int X2 = abs(x2);
		int Y2 = abs(y2);
 
		// 1111
		if(x2 > 0 && y2 > 0){
			ans += Hal1(x1, y1, X2, Y2);
			// d2(1, ans);
		}
 
		// 2222
		if(x1 <= 0 && y2 > 0){
			ans += Hal2(x2, y1, X1, Y2);
			// d2(2, ans);
		}
 
		// 33333
		if(x1 <= 0 && y1 <= 0){
			ans += Hal3(x2, y2, X1, Y1);
			// d2(3, ans);
		}
		
		// 4444
		if(x2 > 0 && y1 <= 0){
			ans += Hal4(x1, y2, X2, Y1);
			// d2(4, ans);
		}
 
		ans %= MOD;
		ans += MOD;
		ans %= MOD;
 
		cout << ans << endl;
	}
}
 
// Ey To Bahane! :_)))
 
// -------------<3------------- //
/*
Magasan dor shirini: 
 
1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 
 
*/
 
/*
1000000000 1
-1 0 -1 1
*/

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25