| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1047108 |
2024-08-07T09:00:26 Z |
danya111 |
Spiral (BOI16_spiral) |
C++17 |
|
1 ms |
348 KB |
//#pragma gcc optimize("O3,Ofast,no-stack-protector,fast-math,section-anchors,inline,unroll-loops")
//#pragma gcc target("abm,mmx,sse,sse2,sse3,sse4,ssse3,tune=native,lzcnt,popcnt,avx,avx2")
//#include<immintrin.h>
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<array>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<tuple>
#include<cmath>
#include<deque>
#include<ctime>
#include<random>
#include<bitset>
#include<unordered_map>
#include<unordered_set>
#include<chrono>
#include<queue>
#include<fstream>
#include<cassert>
using namespace std;
using ll = long long;
using ld = long double;
using li = __int128;
using ui = unsigned int;
using ul = unsigned long long;
#define ft first
#define sc second
#define all(x) x.begin(), x.end()
template <typename T1, typename T2> ostream& operator << (ostream &c, const pair<T1, T2> &v);
template <typename T> ostream& operator << (ostream &c, const vector<T> &v) {
c << '{';
for (int i = 0; i < v.size(); i++) {
c << v[i];
if (i+1 != v.size()) c << ", ";
}
c << '}';
return c;
}
template <typename T1, typename T2> ostream& operator << (ostream &c, const pair<T1, T2> &v) {
c << '<' << v.ft << ", " << v.sc << '>';
return c;
}
ostream& operator << (ostream &c, li x) {
if (x == 0) {
c << 0;
return c;
}
if (x < 0) {
c << '-';
x = -x;
}
auto f = [](auto &f, ostream &c, li x)->void {
if (x == 0) return;
f(f, c, x/10);
c << int(x%10);
};
f(f, c, x);
return c;
}
#define debug(x) cout << (#x) << " = " << x << endl;
const ll inf = 1e18, mod = 1e9+7, N = 100;
const long double pi = acos(-1);
ll n = 2;
li f1(li x, li j) {
return x*j*(j-1)/2 + j*(x*(8*x*x-3*x+7)/6) + (x*(x+1)*(6*x*x-5*x+2)/6);
}
li f2(li x, li i) {
return (x+1)*i*(i-1)/2 + i*((x+1)*(8*x*x+31*x+42)/6) - ((x+1)*x*(6*x*x+25*x+29)/6);
}
li f3(li x, li j) {
return (x+1)*j*(j-1)/2 + j*((x+1)*(8*x*x+13*x+12)/6) - (x*(x+1)*(6*x*x+13*x+8)/6);
}
li f4(li x, li i) {
return -(x+1)*i*(i-1)/2 + i*((x+1)*(x+2)*(8*x+3)/6) - (x*(x+1)*(x+1)*(2*x+3)/2);
}
li f5(li x, li i) {
return -(x-1)*i*(i-1)/2 + i*((x-1)*x*(8*x-13)/6) + ((x-1)*(2*x*x*x-x*x-2*x+2)/2);
}
li f6(li x, li j) {
return -(x+1)*j*(j-1)/2 + j*((x+1)*(x+2)*(8*x+9)/6) - ((x+1)*x*(6*x*x+19*x+17)/6);
}
li f7(li x, li j) {
return -(x-1)*j*(j-1)/2 + j*((x-1)*x*(8*x-7)/6) + ((x-1)*(6*x*x*x+x*x-2*x+6)/6);
}
li f8(li x, li i) {
return x*i*(i-1)/2 + i*(x*(8*x*x+15*x+19)/6) + (x*(x+1)*(6*x*x+7*x+5)/6);
}
li solve(int i, int j) {
if (i < -n || j < -n) return 0;
li ans = 0;
if (i >= -j && i >= 0) {
///!!!!!!!
ans += f1(i+1, j)-f1(max(-j, 0), j);
//cout << "1 " << f1(i+1, j)-f1(max(-j, 0), j) << "\n";
if (i > 0) {
ans -= f2(i-1, i)-f2(max(-j-1, 0)-1, i);
//cout << "2 " << f2(i-1, i)-f2(max(-j-1, 0)-1, i) << "\n";
}
}
if (i >= 0 && j >= 1) {
ans -= f3(min(i, j-1), j);
//cout << "3 " << f3(min(i, j-1), j) << "\n";
ans -= f4(min(i, j-1), i);
//cout << "4 " << f4(min(i, j-1), i) << "\n";
}
if (i >= -j && j > 0) {
ans += f5(j+1, i)-f5(max(-i+1, 2)-1, i);
//cout << "5 " << f5(j+1, i)-f5(max(-i+1, 2)-1, i) << "\n";
ans -= f6(j-1, j)-f6(max(-i+1, 2)-3, j);
//cout << "6 " << f6(j-1, j)-f6(max(-i+1, 2)-3, j) << "\n";
}
ans += f7(n+1, j)-f7(max(-min(i, j), 1), j);
//cout << "7 " << f7(n+1, j)-f7(max(-min(i, j), 1), j) << "\n";
ans += f8(n, i)-f8(max(-min(i, j)-1, 0), i);
//cout << "8 " << f8(n, i)-f8(max(-min(i, j)-1, 0), i) << "\n";
return ans;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("1B/tests/152", "r", stdin);
//freopen("macloren.txt", "w", stdout)
mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
int q, x1, y1, x2, y2;
cin >> n >> q;
while (q--) {
cin >> x1 >> y1 >> x2 >> y2;
swap(y1, y2); y1 = -y1; y2 = -y2; swap(x1, y1); swap(x2, y2);
//cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
li res = solve(x2, y2) - solve(x2, y1-1) - solve(x1-1, y2) + solve(x1-1, y1-1);
cout << (res%mod+mod)%mod << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
