Submission #1102578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102578		ttamx	Game (IOI13_game)	C++17	63 / 100	902 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll gcd2(ll X,ll Y){
    while(Y!=0)tie(X,Y)=make_pair(Y,X%Y);
    return X;
}

int n,m;

struct Node{
    ll val;
    int l,r;
    Node():val(0LL),l(0),r(0){}
}node[16000000];

int cur_node=0;

struct SegTree{
    int root;
    SegTree():root(0){}
    ll get(int t){
        return t?node[t].val:0LL;
    }
    void modify(int l,int r,int &t,int x,ll v){
        if(!t)t=++cur_node;
        if(l==r)return void(node[t].val=v);
        int m=(l+r)/2;
        if(x<=m)modify(l,m,node[t].l,x,v);
        else modify(m+1,r,node[t].r,x,v);
        node[t].val=gcd2(get(node[t].l),get(node[t].r));
    }
    void modify(int x,ll v){
        modify(0,m-1,root,x,v);
    }
    ll query(int l,int r,int &t,int x,int y){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].val;
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y),query(m+1,r,node[t].r,x,y));
    }
    ll query(int x,int y){
        return query(0,m-1,root,x,y);
    }
};

struct SegTree2D{
    struct Node;
    using Ptr = Node*;
    struct Node{
        SegTree tree;
        Ptr l,r;
        Node():tree(),l(),r(){}
    };
    Ptr root;
    SegTree2D():root(){}
    ll get(Ptr t,int x){
        return t?t->tree.query(x,x):0LL;
    }
    void modify(int l,int r,Ptr &t,int x,int y,ll v){
        if(!t)t=new Node();
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,t->l,x,y,v);
            else modify(m+1,r,t->r,x,y,v);
            v=gcd2(get(t->l,y),get(t->r,y));
        }
        t->tree.modify(y,v);
    }
    void modify(int x,int y,ll v){
        modify(0,n-1,root,x,y,v);
    }
    ll query(int l,int r,Ptr &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return t->tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,t->l,x,y,x2,y2),query(m+1,r,t->r,x,y,x2,y2));
    }
    ll query(int x,int y,int x2,int y2){
        return query(0,n-1,root,x,y,x2,y2);
    }
}seg;

void init(int R,int C){
    n=R,m=C;
}

void update(int P,int Q,ll K){
    seg.modify(P,Q,K);
}

ll calculate(int P,int Q,int U,int V){
    return seg.query(P,U,Q,V);
}

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