제출 #871138

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

game

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "game.h"
using namespace std;
int n,m,q;
ll x,y,k,type,X1,Y1,X2,Y2;
ll GCD(ll a,ll b)
{
    if(a==0 && b==0) return 0;
    if(a==0) return b;
    while(b>0)
    {
        ll r=a%b;
        a=b;
        b=r;
    }
    return a;
}
struct _1D_node
{
    _1D_node *left,*right;
    ll res=0;
    void comp()
    {
        res=GCD(left==NULL ? 0 : left->res,right==NULL ? 0 : right->res);
    }
} *L,*R;
_1D_node *get_left(_1D_node *u) { return (u==NULL) ? NULL : u->left; }
_1D_node *get_right(_1D_node *u) { return (u==NULL) ? NULL : u->right; }
ll get_res(_1D_node *u) { return (u==NULL) ? 0 : u->res; }
_1D_node *_1D_update(_1D_node *u,int l,int r)
{
    if(u==NULL) u=new _1D_node();
    if(l==r) { u->res=k; return u; }
    int mid=(l+r)>>1;
    if(y<=mid) u->left=_1D_update(u->left,l,mid);
    else u->right=_1D_update(u->right,mid+1,r);
    u->comp();
    return u;
}
ll _1D_get(_1D_node *u,int l,int r)
{
    if(Y1>r || Y2<l || u==NULL) return 0;
    if(Y1<=l && r<=Y2) return u->res;
    int mid=(l+r)>>1;
    if(Y2<=mid) return _1D_get(u->left,l,mid);
    if(Y1>mid) return _1D_get(u->right,mid+1,r);
    return GCD(_1D_get(u->left,l,mid),_1D_get(u->right,mid+1,r));
}
_1D_node *_1D_comp(_1D_node *u,int l,int r)
{
    if(u==NULL) u=new _1D_node();
    u->res=GCD(get_res(L),get_res(R));
    if(l==r) return u;
    int mid=(l+r)>>1;
    if(y<=mid)
    {
        L=get_left(L);
        R=get_left(R);
        u->left=_1D_comp(u->left,l,mid);
    }
    else
    {
        L=get_right(L);
        R=get_right(R);
        u->right=_1D_comp(u->right,mid+1,r);
    }
    return u;
}




struct _2D_node
{
    _2D_node *left,*right;
    _1D_node *Tree;
} *_2D_root;

_1D_node *get_Tree(_2D_node *u) { return (u==NULL ? NULL : u->Tree); }
_2D_node *_2D_update(_2D_node *u,int l,int r)
{
    if(u==NULL) u=new _2D_node();
    if(l==r) { u->Tree=_1D_update(u->Tree,1,m); return u; }
    int mid=(l+r)>>1;
    if(x<=mid) u->left=_2D_update(u->left,l,mid);
    else u->right=_2D_update(u->right,mid+1,r);
    L=get_Tree(u->left); R=get_Tree(u->right);
    u->Tree=_1D_comp(u->Tree,1,m);
    return u;
}
ll _2D_get(_2D_node *u,int l,int r)
{
    if(X1>r || X2<l || u==NULL) return 0;
    if(X1<=l && r<=X2) return _1D_get(u->Tree,1,m);
    int mid=(l+r)>>1;
    return GCD(_2D_get(u->left,l,mid),_2D_get(u->right,mid+1,r));
}

void init(int _n,int _m)
{
    n=_n; m=_m;
}
void update(int _x,int _y,ll _k)
{
    x=_x+1; y=_y+1; k=_k;
    _2D_root=_2D_update(_2D_root,1,n);
}
ll calculate(int _x1,int _y1,int _x2,int _y2)
{
    X1=_x1+1; Y1=_y1+1; X2=_x2+1; Y2=_y2+1;
    return _2D_get(_2D_root,1,n);
}

/*
int main()
{
    freopen("game.inp","r",stdin);
    freopen("game.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    init(n,m);
    while(cin>>type)
        if(type==1) cin>>x>>y>>k,update(x,y,k);
        else
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<calculate(x1,y1,x2,y2)<<'\n';
        }
}


*/

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