제출 #1008742

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1008742		CYMario	게임 (IOI13_game)	C++17	80 / 100	2876 ms	256000 KiB

game

#include <stdio.h>
#include <algorithm>
#include "game.h"
#define getchar getchar_unlocked
#define putchar putchar_unlocked
typedef long long i64;
i64 gcd(i64 a, i64 b)
{
    // a = std::abs(a), b = std::abs(b);
    if (!a || !b)
        return a | b;
	int az = __builtin_ctzll(a), bz = __builtin_ctzll(b), z = std::min(az, bz);
	b >>= bz;
	while (a)
	{
		a >>= az;
		i64 d = std::abs(a - b);
		az = __builtin_ctzll(d);
		if (a < b)
			b = a;
		a = d;
	}
	return b << z;
}
const int N = 22010, V = 1000000010, LOG_V = 30;
// Dynamic 2D seg
// exterior : x inner : y
namespace dyna_seg_2d
{
    int XL, XR, YL, YR;
    void init(int _XL, int _XR, int _YL, int _YR) { XL = _XL, XR = _XR, YL = _YL, YR = _YR; }

    int root;
    struct node_x 
    { 
        int lc, rc;
        int rt; // root for inner dimension
    } ptx[N * (LOG_V + 1)];
    int cnt_x;
    
    struct node_y
    {
        int lc, rc;
        i64 sum; // real info in inner
    } pty[N * (LOG_V + 1) * (LOG_V + 1)];
    int cnt_y;

    void pushup_y(int u) { pty[u].sum = gcd(pty[pty[u].lc].sum, pty[pty[u].rc].sum); }

    void modify_y(int& u, int yl, int yr, const int& x, const int& y, const i64& val)
    {
        if (!u)
            u = ++cnt_y;
        if (yl == yr)
        {
            pty[u].sum = val;
            return;
        }  
        int ym = (yl + yr) >> 1;
        if (y <= ym)
            modify_y(pty[u].lc, yl, ym, x, y, val);
        else
            modify_y(pty[u].rc, ym + 1, yr, x, y, val);
        pushup_y(u);
    }

    void pushup_x(int &u, int xlc, int xrc, int yl, int yr, int y)
    {
        if (!u)
            u = ++cnt_y;
        if (yl == yr)
        {
            pty[u].sum = gcd(pty[xlc].sum, pty[xrc].sum);
            return;
        }
        int ym = (yl + yr) >> 1;
        if (y <= ym)
            pushup_x(pty[u].lc, pty[xlc].lc, pty[xrc].lc, yl, ym, y);
        else
            pushup_x(pty[u].rc, pty[xlc].rc, pty[xrc].rc, ym + 1, yr, y);
        pushup_y(u);
    }

    void modify_x(int& u, int xl, int xr, const int& x, const int& y, const i64& val)
    {
        if (!u) // dynamic add
            u = ++cnt_x;
        
        if (xl == xr)
        {
            modify_y(ptx[u].rt, YL, YR, x, y, val);
            return;
        }

        int xm = (xl + xr) >> 1;
        if (x <= xm)
            modify_x(ptx[u].lc, xl, xm, x, y, val);
        else
            modify_x(ptx[u].rc, xm + 1, xr, x, y, val);
        pushup_x(ptx[u].rt, ptx[ptx[u].lc].rt, ptx[ptx[u].rc].rt, YL, YR, y);
    }
    // [y1, y2] for query [yl, yr] for cur node
    i64 query_y(int u, int yl, int yr, const int& y1, const int& y2)
    {
        if (yr < y1 || yl > y2 || !u)
            return 0;
        if (y1 <= yl && yr <= y2)
            return pty[u].sum;
        int ym = (yl + yr) >> 1;
        return gcd(query_y(pty[u].lc, yl, ym, y1, y2), query_y(pty[u].rc, ym + 1, yr, y1, y2));
    }
    i64 query_x(int u, int xl, int xr, const int& x1, const int& x2, const int& y1, const int& y2)
    {
        if (xr < x1 || xl > x2 || !u)
            return 0;
        if (x1 <= xl && xr <= x2)
            return query_y(ptx[u].rt, YL, YR, y1, y2);
        int xm = (xl + xr) >> 1;
        return gcd(query_x(ptx[u].lc, xl, xm, x1, x2, y1, y2), query_x(ptx[u].rc, xm + 1, xr, x1, x2, y1, y2));
    }

    void modify(int x, int y, i64 val) { modify_x(root, XL, XR, x, y, val); }
    i64 query(int x1, int x2, int y1, int y2) { return query_x(root, XL, XR, x1, x2, y1, y2); }
}

void init(int R, int C) { dyna_seg_2d::init(0, R - 1, 0, C - 1); }
 
void update(int P, int Q, i64 K) { dyna_seg_2d::modify(P, Q, K); }
 
i64 calculate(int P, int Q, int U, int V) { return dyna_seg_2d::query(P, U, Q, V); }

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

game.cpp: In function 'i64 gcd(i64, i64)':
game.cpp:10:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   10 |     if (!a || !b)
      |     ^~
game.cpp:12:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   12 |  int az = __builtin_ctzll(a), bz = __builtin_ctzll(b), z = std::min(az, bz);
      |  ^~~

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