제출 #871131

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
871131		HuyQuang_re_Zero	게임 (IOI13_game)	C++14	63 / 100	1121 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;
ll GCD(ll a,ll b) { return (a==0 && b==0) ? 0 : __gcd(a,b); }
struct _1D_node
{
    _1D_node *left,*right;
    ll res=0;
    void comp()
    {
        res=GCD(left==NULL ? 0 : left->res,right==NULL ? 0 : right->res);
    }
};
_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,int y,ll k)
{
    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,y,k);
    else u->right=_1D_update(u->right,mid+1,r,y,k);
    u->comp();
    return u;
}
ll _1D_get(_1D_node *u,int l,int r,int y1,int y2)
{
    if(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,y1,y2);
    if(y1>mid) return _1D_get(u->right,mid+1,r,y1,y2);
    return GCD(_1D_get(u->left,l,mid,y1,mid),_1D_get(u->right,mid+1,r,mid+1,y2));
}
_1D_node *_1D_comp(_1D_node *u,_1D_node *left,_1D_node *right,int l,int r,int y)
{
    if(u==NULL) u=new _1D_node();
    u->res=GCD(get_res(left),get_res(right));
    if(l==r) return u;
    int mid=(l+r)>>1;
    if(y<=mid) u->left=_1D_comp(u->left,get_left(left),get_left(right),l,mid,y);
    else u->right=_1D_comp(u->right,get_right(left),get_right(right),mid+1,r,y);
    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,int x,int y,ll k)
{
    if(u==NULL) u=new _2D_node();
    if(l==r) { u->Tree=_1D_update(u->Tree,1,m,y,k); return u; }
    int mid=(l+r)>>1;
    if(x<=mid) u->left=_2D_update(u->left,l,mid,x,y,k);
    else u->right=_2D_update(u->right,mid+1,r,x,y,k);
    u->Tree=_1D_comp(u->Tree,get_Tree(u->left),get_Tree(u->right),1,m,y);
    return u;
}
ll _2D_get(_2D_node *u,int l,int r,int x1,int y1,int x2,int y2)
{
    if(u==NULL) return 0;
    if(x1<=l && r<=x2) return _1D_get(u->Tree,1,m,y1,y2);
    int mid=(l+r)>>1;
    if(x2<=mid) return _2D_get(u->left,l,mid,x1,y1,x2,y2);
    if(x1>mid) return _2D_get(u->right,mid+1,r,x1,y1,x2,y2);
    return GCD(_2D_get(u->left,l,mid,x1,y1,mid,y2),_2D_get(u->right,mid+1,r,mid+1,y1,x2,y2));
}

void init(int _n,int _m)
{
    n=_n; m=_m;
}
void update(int x,int y,ll k)
{
    _2D_root=_2D_update(_2D_root,1,n,x+1,y+1,k);
}
ll calculate(int x1,int y1,int x2,int y2)
{
    return _2D_get(_2D_root,1,n,x1+1,y1+1,x2+1,y2+1);
}

/*
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