I am trying to solve this problem using sqrt_decomposition : http://www.spoj.com/problems/HORRIBLE/ Getting WA

Strategy used : 1. Two arrays, b for storing range sum, c for storing range change. 2. Whenever requested update, range which do not lie completely in a block is individually updated where as for a block range update only c. 3. same can be considered for query.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#define ll long long int
using namespace std;

int n, q, type, x, y, k;
ll a[10000000], b[1000000], c[1000000];
int bs, cnt;

void sqrt_decomposition() {

    bs = (int) sqrt(n + .0) + 1;
    
}

void update(int l, int r, int k) {

    int cl = l / bs, cr = r / bs;

    if(cl == cr) {

        for(int i = l; i <= r; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            b[cl] += k - a[i];
            a[i] += k;
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            c[i] += k;
        }

        for(int i = cr * bs; i <= r; ++i) {
            b[cr] += k - a[i];
            a[i] += k;
        }

    }
}

ll query(int l, int r) {

    int cl = l / bs, cr = r / bs;
    ll sum = 0;

    if(cl == cr) {

        for(int i = l; i <= r; ++i)
            sum += a[i] + c[cl];
    }

    else {

        for(int i = l, end = (cl + 1) * bs - 1; i <= end; ++i) {
            sum += a[i] + c[cl];
        }

        for(int i = (cl + 1); i <= (cr - 1); ++i) {
            sum += b[i] + bs * c[i];
        }

        for(int i = cr * bs; i <= r; ++i) {
            sum += a[i] + c[cr];
        }

    }

    return sum;
}

int main() {

    ios_base::sync_with_stdio(false);

    int test;
    cin >> test;

    while(test--) {

        cin >> n >> q;

        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(c, 0, sizeof(c));

        sqrt_decomposition();

        while(q--) {

            cin >> type;

            if(type) {
                cin >> x >> y;
                cout << query(x - 1, y - 1) << endl;
            }

            else {
                cin >> x >> y >> k;
                update(x - 1, y - 1, k);
            }
        }

    }

    return 0;
}

Please Help.

I am trying to solve this problem : http://www.spoj.com/problems/MATGAME/

I read all the available entries. I can't figure out where is mistake in my code.

Strategy used:

1. Calculated grundy value for each possible cell entry

void solve() {

grundy[0] = 0;

for(int i = 1; i <= 51; ++i) {

    memset(used, false, sizeof(used));

    int mex = 0;
    for(int j = 1; j <= i; ++j)
        used[grundy[i - j]] = true;

    while(used[mex])
        ++mex;

    grundy[i] = mex;
    for(int j = i + 1; j <= 51; ++j)
        grundy[j] = grundy[i];
}

}

1. Then for each row calculated it's grundy number and xor-ed them.

int main() {

solve();

int test, n, m, item;                           // n rows, m columns
scanf("%d", &test);

while(test--) {

    scanf("%d%d", &n, &m);                   
    int gr_overall = 0;                        // NIM sum

    for(int i = 0; i < n; ++i) {

        int mex = 1;                          // Tried mex = 0 also gives WA
        memset(used, false, sizeof(used));

        for(int j = 0; j < m; ++j) {
            scanf("%d", &item);
            used[grundy[item]] = true;         // Marking grundy number for each cell
        }

        while(used[mex]) ++mex;                // Calculating minimum value

        gr_overall ^= mex;                     // Calcualting NIM sum

    }

    if(gr_overall) cout << "FIRST" << endl;
    else cout << "SECOND" << endl;

}

return 0;

}

Please help. Thank you.