제출 #57539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
57539		Crown	게임 (IOI13_game)	C++14	100 / 100	6168 ms	232448 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;

const int maxr = 1e9+5;
const int maxc = 1e9+5; 

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

struct layer2_node
{
    layer2_node(int low, int high) : low(low), high(high), left(NULL), right(NULL), value(0LL) {}
    int low, high;
    layer2_node *left;
    layer2_node *right;
    ll value;   
};

struct layer1_node
{
    layer1_node() : left(NULL), right(NULL), l2(0, maxc) {} 
    layer1_node *left, *right;
    layer2_node l2;
};

static layer1_node root;

static void update2(layer2_node* node, int Q, long long K)
{
    int low = node->low;
    int high = node->high;
    int mid = (low+high)/2;
    if(low == high)
    {
        node->value = K;
        return;
    }

    layer2_node*& tgt = Q<=mid ? node->left : node->right;

    if(tgt == NULL)
    {
        tgt = new layer2_node(Q, Q);
        tgt->value = K;
    }
    else if(tgt->low <= Q && Q<= tgt->high)
    {
        update2(tgt, Q, K);
    }
    else
    {
        do
        {
            if(Q<= mid) high = mid;
            else low = mid+1;
            mid = (low+high)/2;
        }
        while((Q<= mid) == (tgt->low <= mid));

        layer2_node* newnode = new layer2_node(low, high);
        (tgt->low<= mid? newnode->left : newnode->right) = tgt;
        tgt = newnode;

        update2(newnode, Q, K);
    }
    node->value = gcd2(node->left? node->left->value: 0, node->right?node->right->value:0);
}

ll query2(layer2_node *nd, int A, int B)
{
    if(nd == NULL || B< nd->low || A> nd->high) return 0;
    else if(A<= nd->low && nd->high <= B) return nd->value;
    return gcd2(query2(nd->left, A, B), query2(nd->right, A, B));
}

static void update1(layer1_node *node, int low, int high, int P, int Q, ll K)
{
    int mid = (low+high)/2;
    if(low == high)
    {
        update2(&node->l2, Q, K);
    }
    else
    {
        layer1_node*& newnode = P<= mid? node->left : node->right;
        if(P<= mid) high = mid;
        else low = mid+1;
        if(newnode == NULL)
        {
            newnode = new layer1_node();
        }
        update1(newnode, low, high, P, Q, K);
        K = gcd2(node->left?query2(&node->left->l2, Q, Q) : 0, node->right?query2(&node->right->l2, Q, Q) : 0);
        update2(&node->l2, Q, K);
    }
}

ll query1(layer1_node* nd, int low, int high, int A1, int B1, int A2, int B2)
{
    if(nd == NULL || B1< low || high < A1)
    {
        return 0;
    }
    else if(A1<= low && high<= B1)
    {
        return query2(&nd->l2, A2, B2);
    }
    int mid = (low+high)/2;
    return gcd2(query1(nd->left, low, mid, A1, B1, A2, B2), query1(nd->right, mid+1, high, A1, B1, A2, B2));    
}
void init(int R, int C){}
void update(int P, int Q, long long K)
{
    update1(&root, 0, maxr, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query1(&root, 0, maxr, P, U, Q, V);
}

컴파일 시 표준 에러 (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: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20