Submission #254582

#	Time	Username	Problem	Language	Result	Execution time	Memory
254582		AaronNaidu	Game (IOI13_game)	C++14	37 / 100	13081 ms	68968 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll bigNum = 1073741824;
ll mult = 1000000007;
ll r, c, p, q, u, v;
//ll segTree[32][262144];
unordered_map<ll, ll> segTree;
unordered_map<ll, ll> gcds;

void init(int R, int C) {
    r = R;
    c = C;
}

long long gcd2(long long X, long long Y) {
    auto possAns = gcds.find({mult*X+Y});
    if (possAns != gcds.end())
    {
        return possAns->second;
    }
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    gcds.insert({mult*X+Y, X});
    return X;
}

void update(int p, int q, ll k) {
    p += bigNum;
    q += bigNum;
    auto trash = segTree.find(mult * p + q);
    if (trash != segTree.end())
    {
        segTree.erase(trash);
    }
    
    segTree.insert({mult * p + q, k});
    while (q > 0)
    {
        //cout << "Outerwhile q = " << q << "\n";
        ll pTemp = p/2;
        while (pTemp > 0)
        {
            //cout <<"Innerwhile p temp = " << pTemp << "\n";
            auto place1 = segTree.find(mult*2*pTemp + q);
            ll value1;
            if (place1 == segTree.end())
            {
                 value1 = 0;
            }
            else
            {
                value1 = place1->second;
            }

            auto place2 = segTree.find(mult*(2*pTemp+1) + q);
            ll value2;
            if (place2 == segTree.end())
            {
                 value2 = 0;
            }
            else
            {
                value2 = place2->second;
            }
            trash = segTree.find(mult*pTemp + q);
            if (trash != segTree.end())
            {
                segTree.erase(trash);
            }
            
            segTree.insert({mult*pTemp+ q, gcd2(value1, value2)});
            pTemp /= 2;
        }
        q /= 2;
        auto place1 = segTree.find(mult*p + 2*q);
        ll value1;
        if (place1 == segTree.end())
        {
            value1 = 0;
        }
        else
        {
            value1 = place1->second;
        }

        auto place2 = segTree.find(mult*p + 2*q+1);
        ll value2;
        if (place2 == segTree.end())
        {
            value2 = 0;
        }
        else
        {
            value2 = place2->second;
        }
        trash = segTree.find(mult*p+ q);
        if (trash != segTree.end())
        {
            segTree.erase(trash);
        }
        
        segTree.insert({mult*p+q, gcd2(value1, value2) }); 
        //cout << "End of outerwhile q = " << q << "\n";
    }

}

ll getSegTree(ll nodex, ll nodey, ll nodexstart, ll nodexend, ll nodeystart, ll nodeyend) {
    if (nodexstart > u or nodexend < p or nodeystart > v or nodeyend < q)
    {
        return 0;
    }
    if (nodexstart >= p and nodexend <= u)
    {
        if (nodeystart >= q and nodeyend <= v)
        {
            auto ansPlace = segTree.find(mult*nodex + nodey);
            if (ansPlace == segTree.end())
            {
                return 0;
            }
            //cout << "Returning " << nodex << "," << nodey << " which is " << ansPlace->second;
            return ansPlace->second;
        }
        ll midy = (nodeystart + nodeyend)/2;
        return gcd2(getSegTree(nodex, 2*nodey, nodexstart, nodexend, nodeystart, midy), getSegTree(nodex, 2*nodey+1, nodexstart, nodexend, midy+1, nodeyend));
    }
    ll midx = (nodexstart + nodexend)/2;
    return gcd2(getSegTree(2*nodex, nodey, nodexstart, midx, nodeystart, nodeyend), getSegTree(2*nodex+1, nodey, midx + 1, nodexend, nodeystart, nodeyend));
}    
    
ll calculate(int P, int Q, int U, int V) {
    p = P;
    q = Q;
    u = U;
    v = V;
    return getSegTree(1, 1, 0, bigNum-1, 0, bigNum-1);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20