oj.uz

Submission #349441

# Submission time Handle Problem Language Result Execution time Memory
349441 2021-01-17T15:37:56 Z S2speed Spiral (BOI16_spiral) C++17
12 / 100
 1500 ms 65772 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 63744 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 88 ms 65772 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 63744 KB Output is correct
2 Execution timed out 1587 ms 19916 KB Time limit exceeded

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 93 ms 65772 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 63744 KB Output is correct
2 Runtime error 88 ms 65772 KB Execution killed with signal 11 (could be triggered by violating memory limits)