Submission #987439

#	Time	Username	Problem	Language	Result	Execution time	Memory
987439		canadavid1	Game (IOI13_game)	C++17	0 / 100	3 ms	1884 KiB

game

#include "game.h"
template<typename T,typename... Args>
T* New(Args ...args)
{
    static int i=0;
    static T* b = 0;
    if(i<=0)
    {
        b = new T[1<<16];
        i = 1<<16;
    }
    return new(&b[--i]) T(args...);
}

template<typename T>
using ptr = T*;

#include <vector>
#include <utility>


constexpr int MAX = 1e9+10;
using i64 = long long;
i64 gcd2(i64 X,i64 Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct Node
{
    using T = i64;
    T val=0;
    ptr<Node> l,r;
};
i64 query(ptr<Node> n,int l, int r, int rl=0, int rr=MAX)
{
    if(!n) return 0;
    l = std::max(l,rl);
    r = std::min(r,rr);
    if(l==rl && r == rr) return n->val;
    if(l >= r) return 0;
    auto m = (rl+rr)/2;
    return gcd2(query(n->l,l,r,rl,m),query(n->r,l,r,m,rr));
}
ptr<Node> update(ptr<Node> n,i64 val, int p, int rl=0, int rr=MAX)
{
    if(!n) n = New<Node>();
    if(rr-rl == 1)
    {
        n->val = val;
        return n;
    }
    auto m = (rl+rr)/2;
    if(p >= m) n->r = update(n->r,val,p,m,rr);
    else n->l = update(n->l,val,p,rl,m);
    n->val = 0;
    if(n->l) n->val = n->l->val;
    if(n->r) n->val = gcd2(n->val,n->r->val);
    return n;
}

struct Node2d
{
    ptr<Node> val;
    ptr<Node2d> l,r;
};
i64 query(ptr<Node2d> n, int l, int r, int t, int b, int rl=0, int rr=MAX)
{
    if(!n) return 0;
    l = std::max(l,rl);
    r = std::min(r,rr);
    if(l==rl && r == rr) return query(n->val,t,b);
    if(l >= r) return 0;
    auto m = (rl+rr)/2;
    return gcd2(query(n->l,l,r,t,b,rl,m),query(n->r,l,r,t,b,m,rr));
}
ptr<Node2d> update(ptr<Node2d> n, int val, int p, int y, int rl=0, int rr = MAX)
{
    if(!n) n = New<Node2d>();
    if(rr-rl == 1)
    {
        n->val = update(n->val,val,y);
        return n;
    }
    auto m = (rl+rr)/2;
    if(p >= m) n->r = update(n->r,val,p,y,m,rr);
    else n->l = update(n->l,val,p,y,rl,m);
    i64 v = 0;
    if(n->l) v = query(n->l->val,p,p+1);
    if(n->r) v = gcd2(v,query(n->r->val,p,p+1));
    n->val = update(n->val,v,y);
    return n;
}


ptr<Node2d> tree;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    tree = update(tree,K,P,Q);
}

long long calculate(int P, int Q, int U, int V) {
    return query(tree,P,U+1,Q,V+1);
}

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