Submission #351052

#	Time	Username	Problem	Language	Result	Execution time	Memory
351052		Parsa_PG	Spiral (BOI16_spiral)	C++14	0 / 100	152 ms	89304 KiB

spiral

/* Rastegary Az Shoroe Ye EDAST */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
#define int long long
 
using namespace std;
 
const int maxn = 5e3 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const ll inf = 1e18 + 10;

int a[maxn][maxn] , dp[maxn][maxn];
int n , like;
bool vis[maxn][maxn];

bool check(int x , int y){
	return x < n && x >= 0 && y < n && y >= 0;
}

pair<int , int> ce(int x , int y){
	if(like == 0){
		if(check(x - 1 , y) && vis[x - 1][y] == 0){
			like++;
			like = like % 4;
			return {x - 1 , y};
		}else{
			if(check(x , y + 1) && vis[x][y + 1] == 0)
				return {x , y + 1};
			else
				return {-1 , -1};
		}
	}
	if(like == 1){
		if(check(x , y - 1) && vis[x][y - 1] == 0){
			like++;
			like = like % 4;
			return {x , y - 1};
		}else{
			if(check(x - 1, y) && vis[x - 1][y] == 0)
				return {x - 1, y};
			else
				return {-1 , -1};
		}
	}
	if(like == 2){
		if(check(x + 1 , y) && vis[x + 1][y] == 0){
			like++;
			like = like % 4;
			return {x + 1, y};
		}else{
			if(check(x , y - 1) && vis[x][y - 1] == 0)
				return {x, y - 1};
			else
				return {-1 , -1};
		}
	}
	if(like == 3){
		if(check(x , y + 1) && vis[x][y + 1] == 0){
			like++;
			like = like % 4;
			return {x , y + 1};
		}else{
			if(check(x + 1, y) && vis[x + 1][y] == 0)
				return {x + 1, y};
			else
				return {-1 , -1};
		}
	}
	return {-1 , -1};
}

void construct(){
	int i = (n - 1)/2 , j = (n - 1)/2;
	int pt = 1;
	a[i][j] = 1;
	like = 1;
	vis[i][j] = true;
	j++;
	pair<int , int>z;
	while(true){
		pt++;
		vis[i][j] = 1;
		a[i][j] = pt;
		z = ce(i , j);
		if(z.first == -1)
			return;
		i = z.first;
		j = z.second;
	}
}

void PG(){
	dp[0][0] = a[0][0];
	for(int i = 1 ; i < n ; i++){
		dp[i][0] = (dp[i - 1][0] + a[i][0]) % mod;	
		dp[0][i] = (dp[0][i - 1] + a[0][i]) % mod;	
	}
	for(int i = 1 ; i < n ; i++)
		for(int j = 1 ; j < n ; j++)
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + a[i][j]) % mod;
}

int32_t main(){
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> n >> q;
	int nn = n;
	n = 2 * n + 1;
	construct();
	map<int , int>mpx , mpy;
	int pt = nn;
	for(int i = 0 ; i <= nn ; i++){
		mpx[i] = pt; 
		pt--;
	}
	pt = nn + 1;
	for(int i = -1 ; i >= -1 * nn ; i--){
		mpx[i] = pt;
		pt++;
	}
	pt = 0;
	for(int i = -1 * nn ; i <= -1 ; i++){
		mpy[i] = pt;
		pt++;
	}
	for(int i = 0 ; i <= nn ; i++){
		mpy[i] = pt;
		pt++;
	}
	PG();
	while(q--){
		int x1 , x2 , y1 ,y2;
		cin >> y2 >> x2 >> y1 >> x1;
		y2 = mpy[y2];
		y1 = mpy[y1];
		x1 = mpx[x1];
		x2 = mpx[x2];
		int x3 = x2;
		int y3 = y1;
		int ans = (dp[x3][y3] + dp[x1 - 1][y2 - 1]) % mod;
		int xxx = (dp[x2][y2 - 1] + dp[x1 - 1][y1]) % mod;
		ans = (ans - xxx + mod) % mod;
		cout << ans << endl;
	}
	return 0;
}

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