Submission #905142

#	Time	Username	Problem	Language	Result	Execution time	Memory
905142		browntoad	Spiral (BOI16_spiral)	C++14	100 / 100	1 ms	364 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){
    if (x <= 0 || y <= 0) return 0;
    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;
}
int Q2(int x, int y){
    if (x <= 0 || y <= 0) return 0;
    int m = max(x, y);
    // 1
    int ret = y*(x*(x+1)%mod*inv(2)%mod)%mod - x*(y*(y+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, 0, 1, m)-pfp(0, 4, 0, 1, b))%mod;
        ret %= mod;
    }
    ret = (ret%mod+mod)%mod;
    // 3
    ret += pfp(8, -4, 2, -1, b);
    ret = (ret%mod+mod)%mod;
    return ret;
}
int Q3(int x, int y){
    if (x <= 0 || y <= 0) return 0;
    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, 0, 0, -1, b);
    ret = (ret%mod+mod)%mod;
    return ret;
}
int Q4(int x, int y){
    if (x <= 0 || y <= 0) return 0;
    int m = max(x-1, y);

    int ret = y*(x*(x+1)%mod*inv(2)%mod)%mod - x*(y*(y+1)%mod*inv(2)%mod)%mod;
    ret = (ret%mod + mod)%mod;

    int b = min(x-1, y);
    if (x-1 < y){
        ret += x*(pfp(0, 4, 4, 1, m)-pfp(0, 4, 4, 1, x-1))%mod;
        ret %= mod;
    }
    if (x-1 > y){
        ret += y*(pfp(0, 4, 4, 1, m)-pfp(0, 4, 4, 1, y))%mod;
        ret %= mod;
    }
    ret = (ret%mod+mod)%mod;

    ret += pfp(8, 8, 2, 0, b);
    ret = (ret%mod+mod)%mod;
    return ret;
}
int L1(int x){
    if (x <= 0) return 0;
    return pfp(0, 4, -3, 1, x);
}
int L2(int x){
    if (x <= 0) return 0;
    return pfp(0, 4, -1, 1, x);
}
int L3(int x){
    if (x <= 0) return 0;
    return pfp(0, 4, 1, 1, x);
}
int L4(int x){
    if (x <= 0) return 0;
    return pfp(0, 4, 3, 1, x);
}
signed main(){
    IOS();
    cin>>n>>q;
    while(q--){
        int xl, yl, xr, yr; cin>>xl>>yl>>xr>>yr;
        int sm = 0;
        if (xr >= 1 && yr >= 1){
            sm += Q1(xr, yr)-Q1(max(0ll, xl-1), yr)-Q1(xr, max(0ll, yl-1))+Q1(max(0ll, xl-1), max(0ll, yl-1));
            sm %= mod;
        }
        if (xl <= -1 && yr >= 1){
            sm += Q2(-xl, yr)-Q2(max(0ll, -xr-1), yr)-Q2(-xl, max(0ll, yl-1))+Q2(max(0ll, -xr-1), max(0ll, yl-1));
            sm %= mod;
        }
        if (xl <= -1 && yl <= -1){
            sm += Q3(-xl, -yl)-Q3(max(0ll, -xr-1), -yl)-Q3(-xl, max(0ll, -yr-1))+Q3(max(0ll, -xr-1), max(0ll, -yr-1));
            sm %= mod;
        }
        if (xr >= 1 && yl <= -1){
            sm += Q4(xr, -yl)-Q4(max(0ll, xl-1), -yl)-Q4(xr, max(0ll, -yr-1))+Q4(max(0ll, xl-1), max(0ll, -yr-1));
            sm %= mod;
        }
        sm = (sm%mod + mod)%mod;
        if (yl <= 0 && yr >= 0){
            sm += L1(max(xr, 0ll))-L1(max(xl-1, 0ll));
            sm += L3(max(-xl, 0ll))-L3(max(-xr-1, 0ll));
        }
        if (xl <= 0 && xr >= 0){
            sm += L2(max(yr, 0ll))-L2(max(yl-1, 0ll));
            sm += L4(max(-yl, 0ll))-L4(max(-yr-1, 0ll));
        }
        if (xl <= 0 && xr >= 0 && yl <= 0 && yr >= 0){
            sm++;
        }
        sm = (sm%mod + mod)%mod;
        cout<<sm<<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: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 31 / 31
• Subtask 5: 25 / 25