Submission #916423

#	Time	Username	Problem	Language	Result	Execution time	Memory
916423		AverageAmogusEnjoyer	Game (IOI13_game)	C++17	0 / 100	20 ms	1464 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
const int nax = 1e9;
struct node_st2 {
    ll ans=0;
    node_st2 *left_child=nullptr,*right_child=nullptr;
    int l,r;
    node_st2(int _l,int _r) : l(_l) , r(_r) {}  
    void extend() {
        if (!left_child && l != r) {
            int mid = (l+r)/2;
            left_child = new node_st2(l,mid);
            right_child = new node_st2(mid+1,r);
        }
    }
    void upd(int p,ll x) {
        extend();
        ans=gcd(gcd(get_gcd(l,p-1),get_gcd(p+1,r)),x);
        if (left_child) {
            if (p <= left_child->r) {
                left_child->upd(p,x);
            } else {
                right_child->upd(p,x);
            }
        }
    }
    ll get_gcd(int tl,int tr) {
        if (tl <= l && r <= tr) {
            return ans;
        }
        if (tr < l || tl > r) {
            return 0LL;
        }
        extend();
        return gcd(left_child->get_gcd(tl,tr),right_child->get_gcd(tl,tr));
    }
};
struct node_st1 { 
    node_st2 *root;
    node_st1 *left_child=nullptr,*right_child=nullptr;
    int l,r;
    node_st1(int _l,int _r) {
        l = _l;
        r = _r;
        root = new node_st2(0,nax);
    }
    void extend() {
        if (!left_child && l != r) {
            int mid = (l+r)/2;
            left_child = new node_st1(l,mid);
            right_child = new node_st1(mid+1,r);
        }
    }
    void upd(int x,int y,ll nw) {
        extend();
        root->upd(y,nw);
        if (left_child) {
            if (x <= left_child->r) {
                left_child->upd(x,y,nw);
            } else {
                right_child->upd(x,y,nw);
            }
        }
    }
    ll get_gcd(int x1,int y1,int x2,int y2) {
        if (x1 <= l && r <= x2) {
            return root->get_gcd(y1,y2);
        }
        if (x2 < l || x1 > r) { 
            return 0LL;
        }
        extend();
        return gcd(left_child->get_gcd(x1,y1,x2,y2),right_child->get_gcd(x1,y1,x2,y2));
    }
};
node_st1 *root = new node_st1(0,nax);
void init(int r,int c) {
    // AMOGUS
}
void update(int x,int y,ll nw) {
    root->upd(x,y,nw);
}
ll calculate(int x1,int y1,int x2,int y2) {
    return root->get_gcd(x1,y1,x2,y2);
}

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