Submission #1047115

#TimeUsernameProblemLanguageResultExecution timeMemory
1047115danya111Spiral (BOI16_spiral)C++14
100 / 100
1 ms348 KiB
//#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); if (i > 0) ans -= f2(i-1, i)-f2(max(-j-1, 0)-1, i); } if (i >= 0 && j >= 1) { ans -= f3(min(i, j-1), j); ans -= f4(min(i, j-1), i); } if (i >= -j && j > 0) { ans += f5(j+1, i)-f5(max(-i+1, 2)-1, i); ans -= f6(j-1, j)-f6(max(-i+1, 2)-3, j); } ans += f7(n+1, j)-f7(max(-min(i, j), 1), j); ans += f8(n, i)-f8(max(-min(i, j)-1, 0), i); 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); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...