Ikbal has two arrays a and b of length N, initially all values equals to zero.

Question

I was trying to solve this problem with the following code. But the answers aren't accurate for all inputs. Problem Statement

Ikbal has two arrays a and b of length N, initially all values equals to zero. We have Q operation. Let's define three types of operations on this arrays:

1 l r c Increase al,al+1,...,ar by c.

2 l r c Increase bl,bl+1,...,br by c.

3 l r Print (al∗bl)+(al+1∗bl+1)+...+(ar∗br) in modulo 1000000007 Input Format

First line of the input consists of N and Q. Next Q lines contain one of the three types of operations.

Constraints

1≤N≤109 1≤Q≤200000 1≤c≤10000 1≤l≤r≤N Output Format

Whenever you get a type 3 operation, you should print the answer in a new line.

Sample Input

5 3 1 1 5 5 2 2 4 2 3 3 4 Sample Output

20 Explanation

After first operation arrays look like this:

a=5,5,5,5,5

b=0,0,0,0,0 After second operation arrays look like this:

a=5,5,5,5,5

b=0,2,2,2,0

Answer of the third operation: 5∗2+5∗2=20

**MY code **

    #include <cmath>
    #include <cstdio>
    #include <vector>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    int main() {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT */
        vector<int> a,b,c;
        int n,q,r,p;
        cin >> n;
        cin >> q;
        for(int i=0;i<q;i++) {
            cin >> r;
            a.push_back(r);
            if(r==3) {
                p = 3;
            } else {
                p = 4;
            }
                for(int j=1;j<p;j++) {
                    cin >> r;
                    a.push_back(r);
                }
        }
        vector<int> aa(n,0),bb(n,0);
        int g,start,endd,val,anss=0;
        for(int i=0;i<a.size();) {
            if(a[i]==3) {
                start = a[i+1]-1;
                endd = a[i+2]-1;
                if(start==endd) {
                  anss = (aa[start]*bb[start])%1000000007;
                } else {
                anss = (aa[start]*bb[start] + aa[endd]*bb[endd])%1000000007;
                }
                cout << anss << endl;
                i+= 3;
            } else {
                start = a[i+1] - 1;
                endd = a[i+2];
                val = a[i+3];
                if(a[i]==1) {
                    for(int j=start;j<endd;j++) {
                        aa[j] += val;
                    }
                } else {
                        for(int j=start;j<endd;j++) {
                        bb[j] += val;
                    }
                }
                i+= 4;
            }
        }
    /*
        for(int i=0;i<n;i++) {
            cout << aa[i] << " " ;
            cout << bb[i] << endl;
        }
        for(int i=0;i<a.size();i++) {
            cout << a[i] << endl;
        } */
        return 0;
    }

Expected output for given input : https://i.stack.imgur.com/4OsSo.jpg

Answer 1

It's not an overflow problem. This:

if(start==endd)
  anss = (aa[start]*bb[start])%1000000007;
else
  anss = (aa[start]*bb[start] + aa[endd]*bb[endd])%1000000007;

is flat wrong. You misread the instructions.

Answer 2

• Be careful not to cause overflow.
• You have to calculate (al∗bl)+(al+1∗bl+1)+...+(ar∗br), not (al∗bl)+(ar∗br)

At least, the output for the given input

10 20
1 9 9 6768
2 5 5 2202
3 7 7
2 3 9 1167
2 1 7 8465
3 1 5
2 1 1 1860
3 9 9
2 5 5 2153
1 5 7 749
3 1 1
2 8 10 3129
3 1 1
1 2 10 2712
2 1 8 79
1 1 6 4645
1 7 7 1358
3 2 10
1 9 9 8677
3 8 10

is corrected.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int add(int a, int b) {
    int r = a + b;
    if (r >= 1000000007) r -= 1000000007;
    return r;
}

int mul(int a, int b) {
    int r = 0;
    while (b > 0) {
        if (b % 2 != 0) r = add(r, a);
        a = add(a, a);
        b /= 2;
    }
    return r;
}

int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */
    vector<int> a,b,c;
    int n,q,r,p;
    cin >> n;
    cin >> q;
    for(int i=0;i<q;i++) {
        cin >> r;
        a.push_back(r);
        if(r==3) {
            p = 3;
        } else {
            p = 4;
        }
            for(int j=1;j<p;j++) {
                cin >> r;
                a.push_back(r);
            }
    }
    vector<int> aa(n,0),bb(n,0);
    int g,start,endd,val,anss=0;
    for(int i=0;i<a.size();) {
        if(a[i]==3) {
            start = a[i+1]-1;
            endd = a[i+2]-1;
#if 0
            if(start==endd) {
              anss = (aa[start]*bb[start])%1000000007;
            } else {
            anss = (aa[start]*bb[start] + aa[endd]*bb[endd])%1000000007;
            }
#else
            anss = 0;
            if (start <= endd) {
                for(int j=start;j<=endd;j++)anss = add(anss, mul(aa[j], bb[j]));
            } else {
                for(int j=endd;j<=start;j++)anss = add(anss, mul(aa[j], bb[j]));
            }
#endif
            cout << anss << endl;
            i+= 3;
        } else {
            start = a[i+1] - 1;
            endd = a[i+2];
            val = a[i+3];
            if(a[i]==1) {
                for(int j=start;j<endd;j++) {
#if 0
                    aa[j] += val;
#else
                    aa[j] = add(aa[j], val);
#endif
                }
            } else {
                    for(int j=start;j<endd;j++) {
#if 0
                    bb[j] += val;
#else
                    bb[j] = add(bb[j], val);
#endif
                }
            }
            i+= 4;
        }
    }
/*
    for(int i=0;i<n;i++) {
        cout << aa[i] << " " ;
        cout << bb[i] << endl;
    }
    for(int i=0;i<a.size();i++) {
        cout << a[i] << endl;
    } */
    return 0;
}