oj.uz

답안 #1047115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1047115 2024-08-07T09:03:04 Z danya111 Spiral (BOI16_spiral) C++14
100 / 100
 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);
        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";
    }
}

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #5
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct