oj.uz

Submission #368080

# Submission time Handle Problem Language Result Execution time Memory
368080 2021-02-19T12:58:30 Z urd05 Spiral (BOI16_spiral) C++14
31 / 100
 1 ms 364 KB 
#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);
        ret%=mod;
        ret+=mod;
        ret%=mod;
        printf("%lld\n",ret);
    }
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct