Submission #1047108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047108		danya111	Spiral (BOI16_spiral)	C++17	100 / 100	1 ms	348 KiB

spiral

//#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";
    }
}

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