Submission #349444

#	Time	Username	Problem	Language	Result	Execution time	Memory
349444		S2speed	Spiral (BOI16_spiral)	C++17	12 / 100	1560 ms	65228 KiB

spiral

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

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define gcd __gcd 
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
struct piii {
	int first , second , third;
};

const ll MAXN = 2e3 + 20 , md = 1e9 + 7;
 
ll tav(ll n , ll k){
	ll res = 1;
	while(k > 0){
		if(k & 1){
			res *= n;
			res %= md;
		}
		n *= n;
		n %= md;
		k /= 2;
	}
	return res;
}

ll a[MAXN][MAXN] , ps[MAXN][MAXN];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	ll n , v;
	cin>>n>>v;
	if(n > MAXN){
		while(v--){
			ll x1 , x2 , y1 , y2;
			cin>>x1>>y1>>x2>>y2;
			if(x1 == 0 && y1 == 0){
				cout<<"1\n";
				continue;
			}
			ll q = max(abs(x1) , abs(y1)) , p = tav(2 * q - 1 , 2) + 1;
			if(x1 == q && y1 == -q){
				cout<<tav(2 * q + 1 , 2)<<'\n';
				continue;
			}
			if(x1 == q){
				cout<<(p + y1 + q - 1) % md<<'\n';
				continue;
			}
			p += 2 * q - 1;
			if(y1 == q){
				cout<<(p + q - x1) % md<<'\n';
				continue;
			}
			p += 2 * q;
			if(x1 == -q){
				cout<<(p + q - y1) % md<<'\n';
				continue;
			}
			p += 2 * q;
			cout<<(p + x1 + q) % md<<'\n';
		}
	}
	for(ll x1 = -n ; x1 <= n ; x1++){
		for(ll y1 = -n ; y1 <= n ; y1++){
			if(x1 == 0 && y1 == 0){
				a[x1 + n][y1 + n] = 1;
				continue;
			}
			ll q = max(abs(x1) , abs(y1)) , p = tav(2 * q - 1 , 2) + 1;
			if(x1 == q && y1 == -q){
				a[x1 + n][y1 + n] = tav(2 * q + 1 , 2);
				continue;
			}
			if(x1 == q){
				a[x1 + n][y1 + n] = (p + y1 + q - 1) % md;
				continue;
			}
			p += 2 * q - 1;
			if(y1 == q){
				a[x1 + n][y1 + n] = (p + q - x1) % md;
				continue;
			}
			p += 2 * q;
			if(x1 == -q){
				a[x1 + n][y1 + n] = (p + q - y1) % md;
				continue;
			}
			p += 2 * q;
			a[x1 + n][y1 + n] = (p + x1 + q) % md;
		}
	}
	ps[0][0] = a[0][0];
	for(int i = 1 ; i < 2 * n + 1 ; i++){
		ps[i][0] = (ps[i - 1][0] + a[i][0]) % md;
	}
	for(int j = 1 ; j < 2 * n + 1 ; j++){
		ps[0][j] = (ps[0][j - 1] + a[0][j]) % md;
		for(int i = 1 ; i < 2 * n + 1 ; i++){
			ps[i][j] = ps[i][j - 1] + ps[i - 1][j] - ps[i - 1][j - 1] + a[i][j] + md;
			ps[i][j] %= md;
		}
	}
	while(v--){
		ll ans = 0 , x1 , x2 , y1 , y2;
		cin>>x1>>y1>>x2>>y2; swap(x1 , x2); swap(y1 , y2);
		x1 += n;
		x2 += n;
		y1 += n;
		y2 += n;
		ans += ps[x1][y1];
		if(x2 > 0){
			ans -= ps[x2 - 1][y1] - md;
		}
		if(y2 > 0){
			ans -= ps[x1][y2 - 1] - md;
		}
		if(x2 > 0 && y2 > 0){
			ans += ps[x2 - 1][y2 - 1];
		}
		cout<<ans % md<<'\n';
	}
	return 0;
}

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