Submission #1102583

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102583		ttamx	Game (IOI13_game)	C++17	80 / 100	2440 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[14000000];

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{
        SegTree tree;
        int l,r;
        Node():tree(),l(),r(){}
    }node[600000];
    int root,cur_node;
    SegTree2D():root(0),cur_node(0){}
    ll get(int t,int x){
        return t?node[t].tree.query(x,x):0LL;
    }
    void modify(int l,int r,int &t,int x,int y,ll v){
        if(!t)t=++cur_node;
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,node[t].l,x,y,v);
            else modify(m+1,r,node[t].r,x,y,v);
            v=gcd2(get(node[t].l,y),get(node[t].r,y));
        }
        node[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,int &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y,x2,y2),query(m+1,r,node[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: 17 / 17
• Subtask 5: 0 / 20