제출 #365215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365215		Berted	게임 (IOI13_game)	C++17	100 / 100	6386 ms	48084 KiB

game

#include "game.h"

#include <iostream>
#include <algorithm>
#include <vector>
#include <array>

#define ll long long
#define pii pair<int, int>
#define ppi pair<pii, ll>
#define fst first
#define snd second

using namespace std;

inline ll GCD(ll X, ll Y) 
{
    ll tmp;
    while (X != Y && Y != 0) 
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

namespace seg
{
    int r, c;

    vector<pii> Cx; vector<int> Rx;
    pii C[10000000]; int keep[10000001]; 
    ll val[10000000]; 

    int SSZ = 0;

    inline int newNode()
    {
        C[SSZ] = {-1, -1}; keep[SSZ] = -2; SSZ++;
        return SSZ - 1;
    }

    inline int newLine()
    {
        Cx.push_back({-1, -1}); Rx.push_back(-1);
        Rx.back() = newNode();
        return Cx.size() - 1;
    }

    inline void checkChildX(int u, bool b)
    {
        if (b && Cx[u].fst == -1)
        {
            int rr = newLine();
            Cx[u].fst = rr;
        }
        if (!b && Cx[u].snd == -1)
        {
            int rr = newLine();
            Cx[u].snd = rr;
        }
    }

    inline void checkChildY(int u, bool b)
    {
        if (b && C[u].fst == -1)
        {
            int idx = newNode();
            C[u].fst = idx;
        }
        if (!b && C[u].snd == -1)
        {
            int idx = newNode();
            C[u].snd = idx;
        }
    }

    inline int getRoot(int u)
    {
        if (u == -1) {return -1;}
        else {return Rx[u];}
    }

    inline int getChild(int u, bool b)
    {
        if (u == -1) {return -1;}
        else if (b) {return C[u].fst;}
        else {return C[u].snd;}
    }

    inline ll getVal(int u)
    {
        if (u == -1) {return 0;}
        return val[u];
    }

    void updateY(int u, int L, int R, int x, ll v)
    {
        if (L < R && (keep[u] != -2 && keep[u] != x))
        {
            int M = L + R >> 1;
            if (keep[u] != -1)
            {
                checkChildY(u, keep[u] <= M);
                if (keep[u] <= M)
                {
                    val[C[u].fst] = val[u];
                    keep[C[u].fst] = keep[u];
                }
                else
                {
                    val[C[u].snd] = val[u];
                    keep[C[u].snd] = keep[u];
                }
                keep[u] = -1;
            }
            
            checkChildY(u, x <= M);
            if (x <= M) updateY(C[u].fst, L, M, x, v);
            else updateY(C[u].snd, M + 1, R, x, v);
            val[u] = GCD(getVal(C[u].fst), getVal(C[u].snd));
        }
        else {keep[u] = x; val[u] = v;}
    }

    ll queryY(int u, int L, int R, int l, int r)
    {
        l = max(L, l); r = min(R, r);
        if (u == -1) {return 0;}
        if (l <= r)
        {
            if (L == l && R == r) {return val[u];}
            else if (keep[u] != -1)
            {
                if (l <= keep[u] && keep[u] <= r) return val[u];
                else return 0;
            }
            else
            {
                int M = L + R >> 1;
                return GCD(queryY(C[u].fst, L, M, l, r), queryY(C[u].snd, M + 1, R, l, r));
            }
        }
        return 0;
    }

    void updateX(int u, int L, int R, int x, int y, ll v)
    {
        if (L < R)
        {
            int M = L + R >> 1;
            checkChildX(u, x <= M);
            if (x <= M) updateX(Cx[u].fst, L, M, x, y, v);
            else updateX(Cx[u].snd, M + 1, R, x, y, v);
            v = GCD(queryY(getRoot(Cx[u].fst), 0, r - 1, y, y), queryY(getRoot(Cx[u].snd), 0, r - 1, y, y));
        }
        updateY(Rx[u], 0, r - 1, y, v);
    }

    

    ll queryX(int u, int L, int R, int lx, int rx, int ly, int ry)
    {
        lx = max(lx, L); rx = min(rx, R);
        if (u == -1) return 0;
        if (lx <= rx)
        {
            if (L == lx && R == rx) {return queryY(Rx[u], 0, r - 1, ly, ry);}
            else
            {
                int M = L + R >> 1;
                return GCD(queryX(Cx[u].fst, L, M, lx, rx, ly, ry), queryX(Cx[u].snd, M + 1, R, lx, rx, ly, ry));
            }
        }
        return 0;
    }
}

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

void update(int P, int Q, ll K) 
{
    seg :: updateX(0, 0, seg :: c - 1, Q, P, K);
}

long long calculate(int P, int Q, int U, int V) 
{
    return seg :: queryX(0, 0, seg :: c - 1, Q, V, P, U);
}

컴파일 시 표준 에러 (stderr) 메시지

game.cpp: In function 'void seg::updateY(int, int, int, int, long long int)':
game.cpp:102:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  102 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryY(int, int, int, int, int)':
game.cpp:141:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |                 int M = L + R >> 1;
      |                         ~~^~~
game.cpp: In function 'void seg::updateX(int, int, int, int, int, long long int)':
game.cpp:152:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |             int M = L + R >> 1;
      |                     ~~^~~
game.cpp: In function 'long long int seg::queryX(int, int, int, int, int, int, int)':
game.cpp:172:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  172 |                 int M = L + R >> 1;
      |                         ~~^~~

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