Submission #368078

#	Time	Username	Problem	Language	Result	Execution time	Memory
368078		urd05	Spiral (BOI16_spiral)	C++14	0 / 100	1 ms	364 KiB

spiral

#include <bits/stdc++.h>
using namespace std;

const int mod=1e9+7;

long long fastpow(long long a,long long b) {
    long long ret=1;
    while (b!=0) {
        if (b&1) {
            ret*=a;
            ret%=mod;
        }
        b/=2;
        a*=a;
        a%=mod;
    }
    return ret;
}

long long v1(long long x) {
    return ((x*(x+1))/2)%mod;
}

long long v2(long long x) {
    long long ret=x*(x+1);
    ret%=mod;
    ret*=2*x+1;
    ret%=mod;
    ret*=fastpow(6,mod-2);
    ret%=mod;
    return ret;
}

long long v3(long long x) {
    long long ret=v1(x);
    ret*=ret;
    ret%=mod;
    return ret;
}

long long f(long long x2,long long y2) {
    long long temp=min(x2,y2);
    long long ret=8*v3(temp)-24*v2(temp)+24*v1(temp)-7*temp;
    ret%=mod;
    ret+=mod;
    ret%=mod;
    if (x2>=y2) {
        long long val=4*v2(x2)-11*v1(x2)+8*x2;
        val-=4*v2(y2)-11*v1(y2)+8*y2;
        val%=mod;
        val+=mod;
        val%=mod;
        val*=y2;
        val%=mod;
        val+=v1(y2-1)*(x2-y2);
        val%=mod;
        ret+=val;
        ret%=mod;
    }
    else {
        long long val=4*v2(y2)-9*v1(y2)+6*y2;
        val-=4*v2(x2)-9*v1(x2)+6*x2;
        val%=mod;
        val+=mod;
        val%=mod;
        val*=x2;
        val%=mod;
        val-=v1(x2-1)*(y2-x2);
        val%=mod;
        val+=mod;
        val%=mod;
        ret+=val;
        ret%=mod;
    }
    return ret;
}
 
int main(void) {
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=0;i<q;i++) {
        int x1,x2,y1,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        x2++;
        y2++;
        long long ret=f(x2,y2)-f(x1,y2)-f(x2,y1)+f(x1,y1);
        printf("%lld\n",ret);
    }
}

Compilation message (stderr)

spiral.cpp: In function 'int main()':
spiral.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   80 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
spiral.cpp:83:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |         scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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