제출 #904946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
904946		browntoad	Spiral (BOI16_spiral)	C++14	31 / 100	1 ms	600 KiB

spiral

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pip pair<int, pii>
#define ppi pair<pii, int>
#define pdd pair<double ,double>
#define pcc pair<char, char>
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=5005;
const ll maxm=5e4+5;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    if (p < 0) return 0;
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2,m);
}



int n, q;
int pfp(int c3, int c2, int c1, int c0, int b){ // 1 to b
    if (b == 0) return 0;
    int ret = b*c0%mod;
    ret += b*(b+1)%mod*inv(2)%mod*c1%mod;
    ret %= mod;
    ret += b*(b+1)%mod*(2*b+1)%mod*inv(6)%mod*c2%mod;
    ret %= mod;
    ret += SQ(b*(b+1)%mod*inv(2)%mod)%mod*c3%mod;
    ret = (ret%mod+mod)%mod;
    return ret;
}
int Q1(int x, int y){
    int m = max(x, y);
    // 1
    int ret = x*(y*(y+1)%mod*inv(2)%mod)%mod - y*(x*(x+1)%mod*inv(2)%mod)%mod;
    ret = (ret%mod+mod)%mod;
    // 2
    int b = min(x, y);
    if (b < m){
        ret += b*(pfp(0, 4, -2, 1, m)-pfp(0, 4, -2, 1, b))%mod;
        ret %= mod;
    }
    ret = (ret%mod+mod)%mod;
    // 3
    ret += pfp(8, -8, 4, -1, b);
    ret = (ret%mod+mod)%mod;
    return ret;
}

signed main(){
    IOS();
    cin>>n>>q;
    while(q--){
        int xl, yl, xr, yr; cin>>xl>>yl>>xr>>yr;
        cout<<Q1(xr, yr)<<endl;
    }
}
/*
69 10
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 1
1 1 2 2
1 1 2 3
1 1 3 1
1 1 3 2
1 1 3 3
1 1 4 3
*/

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