제출 #254286

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
254286		AaronNaidu	게임 (IOI13_game)	C++14	37 / 100	13100 ms	96472 KiB

game

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

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

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

void update(int p, int q, ll k) {
    p += bigNum;
    q += bigNum;
    auto trash = segTree.find({p, q});
    if (trash != segTree.end())
    {
        segTree.erase(trash);
    }
    
    segTree.insert({{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({2*pTemp, q});
            ll value1;
            if (place1 == segTree.end())
            {
                 value1 = 0;
            }
            else
            {
                value1 = place1->second;
            }

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

        auto place2 = segTree.find({p, 2*q+1});
        ll value2;
        if (place2 == segTree.end())
        {
            value2 = 0;
        }
        else
        {
            value2 = place2->second;
        }
        trash = segTree.find({p, q});
        if (trash != segTree.end())
        {
            segTree.erase(trash);
        }
        
        segTree.insert({{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({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);
}

컴파일 시 표준 에러 (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