Submission #950308

#	Time	Username	Problem	Language	Result	Execution time	Memory
950308		LittleOrange	Spiral (BOI16_spiral)	C++17	100 / 100	2 ms	356 KiB

spiral

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;
ll rev(ll x){
    ll p = mod-2;
    ll r = 1;
    while(p){
        if(p&1) r=r*x%mod;
        x=x*x%mod;
        p>>=1;
    }
    return r;
}
struct l{
    ll x;
    l():x(0){}
    l(const ll &y):x((y+mod)%mod){}
    l(const int &y):x(((ll)y+mod)%mod){}
    l operator+(const l &o)const{
        return l(x+o.x);
    }
    l operator-(const l &o)const{
        return l(x-o.x);
    }
    l operator*(const l &o)const{
        return l(x*o.x);
    }
    l operator/(const l &o)const{
        return l(x*rev(o.x));
    }
    l operator+(const int &o)const{
        return l(x+o);
    }
    l operator-(const int &o)const{
        return l(x-o);
    }
    l operator*(const int &o)const{
        return l(x*o);
    }
    l operator/(const int &o)const{
        return l(x*rev(o));
    }
    operator ll() const{
        return x;
    }
};
l func(l n, const vector<l> v){
    l ret = 0;
    l div = 1;
    l m = 1;
    for(ll i = 0;i<v.size();i++){
        m = m*(n-i);
        div = div*(i+1);
        //cout << v[i] << "*" << m << "/" << div << "\n";
        ret = ret+m*v[i]/div;
    }
    return ret;
}
l line(l n, l add){ // right 1 up 3 left 5 down 7
    //cerr << "line " << n << " " << add << endl;
    return func(n,{1,add,8});//n*(n-1)*(n-2)*8/6+n+n*(n-1)*add/2;
}
l grid(l w, l h){
    return h*w*(w-1)/2;
}
ll get(ll x, ll y){
    ll h = max(abs(x),abs(y));
    ll cur = (h*2+1)*(h*2+1);
    if(y==-h) cur -= h-x;
    else if (x==-h) cur -= h*2+h+y;
    else if (y==h) cur -= h*4+h+x;
    else cur -= h*6+h-y;
    return cur;
}
/*
++ 1, 8, 48, 48
+- 1, 18, 56, 48
-+ 1, 14, 56, 48
-- 1, 20, 64, 48
*/
l rightup(ll x, ll y){
    //cerr << "rightup " << x << " " << y << endl;
    l h = min(x,y);
    l ret = func(h,{1, 8, 48, 48});
    if (x>y){
        ret = ret+(line(x,1)-line(h,1))*h+grid(h,x-h);
    }
    if(y>x){
        ret = ret+(line(y,3)-line(h,3))*h-grid(h,y-h);
    }
    return ret;
}
l rightdown(ll x, ll y){
    //cerr << "rightup " << x << " " << y << endl;
    l h = min(x,y);
    l ret = func(h,{1, 18, 56, 48});
    if (x>y){
        ret = ret+(line(x,1)-line(h,1))*h-grid(h,x-h);
    }
    if(y>x){
        ret = ret+(line(y,7)-line(h,7))*h+grid(h,y-h);
    }
    return ret;
}
l leftup(ll x, ll y){
    //cerr << "rightup " << x << " " << y << endl;
    l h = min(x,y);
    l ret = func(h,{1, 14, 56, 48});
    if (x>y){
        ret = ret+(line(x,5)-line(h,5))*h-grid(h,x-h);
    }
    if(y>x){
        ret = ret+(line(y,3)-line(h,3))*h+grid(h,y-h);
    }
    return ret;
}
l leftdown(ll x, ll y){
    //cerr << "rightup " << x << " " << y << endl;
    l h = min(x,y);
    l ret = func(h,{1, 20, 64, 48});
    if (x>y){
        ret = ret+(line(x,5)-line(h,5))*h+grid(h,x-h);
    }
    if(y>x){
        ret = ret+(line(y,7)-line(h,7))*h-grid(h,y-h);
    }
    return ret;
}
l solve(const function<l(ll,ll)> &f, ll x1, ll x2, ll y1, ll y2){
    l ret = f(x2,y2)+f(x1-1,y1-1)-f(x2,y1-1)-f(x1-1,y2);
    //cout << "add " << ret << "\n";
    return ret;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,q;
    cin >> n >> q;
    /*
    cout << line(2,1) << " " << line(3,1) << "\n";
    cout << line(2,3) << " " << line(3,3) << "\n";
    cout << line(2,5) << " " << line(3,5) << "\n";
    cout << line(2,7) << " " << line(3,7) << "\n";
    for(ll y = n;y>=-n;y--){
        for(ll x = -n;x<=n;x++){
            ll cur = get(x,y);
            cout << (cur<10?"0":"") << cur << " \n"[x==n];
        }
    }
    for(ll k = 0;k<=n;k++){
        ll sum = 0;
        for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(x,y);
        cout << sum << " \n"[k==n];
    }
    for(ll k = 0;k<=n;k++){
        ll sum = 0;
        for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(x,-y);
        cout << sum << " \n"[k==n];
    }
    for(ll k = 0;k<=n;k++){
        ll sum = 0;
        for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(-x,y);
        cout << sum << " \n"[k==n];
    }
    for(ll k = 0;k<=n;k++){
        ll sum = 0;
        for(ll x = 0;x<=k;x++) for(ll y = 0;y<=k;y++) sum+=get(-x,-y);
        cout << sum << " \n"[k==n];
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=n;j++){
            cout << leftdown(j,i) << " \n"[j==n];
        }
    }
    */
    while(q--){
        ll x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        l ans = 0;
        if(x1>=0){
            if(y1>=0){
                ans = ans+solve(rightup,x1+1,x2+1,y1+1,y2+1);
            }else if(y2<=0){
                ans = ans+solve(rightdown,x1+1,x2+1,-y2+1,-y1+1);
            }else{
                ans = ans+solve(rightup,x1+1,x2+1,2,y2+1);
                ans = ans+solve(rightdown,x1+1,x2+1,1,-y1+1);
            }
        }else if(x2<=0){
            if(y1>=0){
                ans = ans+solve(leftup,-x2+1,-x1+1,y1+1,y2+1);
            }else if(y2<=0){
                ans = ans+solve(leftdown,-x2+1,-x1+1,-y2+1,-y1+1);
            }else{
                ans = ans+solve(leftup,-x2+1,-x1+1,2,y2+1);
                ans = ans+solve(leftdown,-x2+1,-x1+1,1,-y1+1);
            }
        }else{
            if(y1>=0){
                ans = ans+solve(rightup,2,x2+1,y1+1,y2+1);
                ans = ans+solve(leftup,1,-x1+1,y1+1,y2+1);
            }else if(y2<=0){
                ans = ans+solve(rightdown,2,x2+1,-y2+1,-y1+1);
                ans = ans+solve(leftdown,1,-x1+1,-y2+1,-y1+1);
            }else{
                ans = ans+solve(rightup,2,x2+1,2,y2+1);
                ans = ans+solve(rightdown,2,x2+1,1,-y1+1);
                ans = ans+solve(leftup,1,-x1+1,2,y2+1);
                ans = ans+solve(leftdown,1,-x1+1,1,-y1+1);
            }
        }
        cout << ans << "\n";
    }
}

Compilation message (stderr)

spiral.cpp: In function 'l func(l, std::vector<l>)':
spiral.cpp:52:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<l>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(ll i = 0;i<v.size();i++){
      |                  ~^~~~~~~~~
spiral.cpp:53:18: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
   53 |         m = m*(n-i);
      |                  ^
spiral.cpp:35:7: note: candidate 1: 'l l::operator-(const int&) const'
   35 |     l operator-(const int &o)const{
      |       ^~~~~~~~
spiral.cpp:53:18: note: candidate 2: 'operator-(ll {aka long long int}, ll {aka long long int})' (built-in)
   53 |         m = m*(n-i);
      |                  ^
spiral.cpp:54:23: warning: ISO C++ says that these are ambiguous, even though the worst conversion for the first is better than the worst conversion for the second:
   54 |         div = div*(i+1);
      |                       ^
spiral.cpp:38:7: note: candidate 1: 'l l::operator*(const int&) const'
   38 |     l operator*(const int &o)const{
      |       ^~~~~~~~
spiral.cpp:54:23: note: candidate 2: 'operator*(ll {aka long long int}, ll {aka long long int})' (built-in)
   54 |         div = div*(i+1);
      |                       ^

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