제출 #110249

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
110249		arnold518	게임 (IOI13_game)	C++14	63 / 100	3137 ms	257024 KiB

game

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int r, c;

struct Node1
{
    Node1() : val(0), lc(NULL), rc(NULL) {}
    ll val; Node1 *lc, *rc;
};

struct Node2
{
    Node2() : val(NULL), lc(NULL), rc(NULL) {}
    Node1 *val; Node2 *lc, *rc;
};

Node2 *root;

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

void update1(Node1* node, int tl, int tr, int x, ll val)
{
    if(tl==tr) { node->val=val; return; }
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(node->lc==NULL) node->lc=new Node1();
        update1(node->lc, tl, mid, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node1();
        update1(node->rc, mid+1, tr, x, val);
    }
    node->val=0;
    if(node->lc!=NULL) node->val=__gcd(node->val, node->lc->val);
    if(node->rc!=NULL) node->val=__gcd(node->val, node->rc->val);
}

ll query1(Node1* node, int tl, int tr, int lx, int rx)
{
    if(tr<lx || rx<tl) return 0;
    if(lx<=tl && tr<=rx) return node->val;
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query1(node->lc, tl, mid, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query1(node->rc, mid+1, tr, lx, rx));
    return ret;
}

void update2(Node2* node, int tl, int tr, int y, int x, ll val)
{
    if(node->val==NULL) node->val=new Node1();
    if(tl==tr) { update1(node->val, 1, c, x, val); return; }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(node->lc==NULL) node->lc=new Node2();
        update2(node->lc, tl, mid, y, x, val);
    }
    else
    {
        if(node->rc==NULL) node->rc=new Node2();
        update2(node->rc, mid+1, tr, y, x, val);
    }
    ll t=0;
    if(node->lc!=NULL) t=__gcd(t, query1(node->lc->val, 1, c, x, x));
    if(node->rc!=NULL) t=__gcd(t, query1(node->rc->val, 1, c, x, x));
    update1(node->val, 1, c, x, t);
}

ll query2(Node2 *node, int tl, int tr, int ly, int ry, int lx, int rx)
{
    if(tr<ly || ry<tl) return 0;
    if(ly<=tl && tr<=ry && node->val!=NULL) return query1(node->val, 1, c, lx, rx);
    int mid=tl+tr>>1;
    ll ret=0;
    if(node->lc!=NULL) ret=__gcd(ret, query2(node->lc, tl, mid, ly, ry, lx, rx));
    if(node->rc!=NULL) ret=__gcd(ret, query2(node->rc, mid+1, tr, ly, ry, lx, rx));
    return ret;
}

void update(int P, int Q, ll K)
{
    P++; Q++;
    update2(root, 1, r, P, Q, K);
}

ll calculate(int P, int Q, int U, int V)
{
    P++; Q++; U++; V++;
    return query2(root, 1, r, 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;
      ^~~
game.cpp: In function 'void update1(Node1*, int, int, int, ll)':
game.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(Node1*, int, int, int, int)':
game.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(Node2*, int, int, int, int, ll)':
game.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(Node2*, int, int, int, int, int, int)':
game.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~

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