| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 349445 |
2021-01-17T15:41:03 Z |
S2speed |
Spiral (BOI16_spiral) |
C++17 |
|
142 ms |
63596 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';
}
return 0;
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
63596 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
63596 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
63596 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
