Submission #924899

#	Time	Username	Problem	Language	Result	Execution time	Memory
924899		12345678	Game (IOI13_game)	C++17	0 / 100	3 ms	860 KiB

game

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

using namespace std;

#define ll long long

const int nx=1e9+5;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct segtree
{
    struct node
    {
        ll vl;
        node *l, *r, *t;
        node(): vl(0), l(0), r(0), t(0){}
    };
    typedef node* pnode;
    pnode rt=0;
    ll value(pnode x) {return x?x->vl:0;}
    void updatey(int l, int r, pnode &k, int y, ll vl)
    {
        if (!k) k=new node();
        if (l==r) return k->vl=vl, void();
        int md=(l+r)/2;
        if (y<=md) updatey(l, md, k->l, y, vl);
        else updatey(md+1, r, k->r, y, vl);
        k->vl=gcd2(value(k->l), value(k->r));
    }
    void updatex(int l, int r, pnode &k, int x, int y, ll vl)
    {
        //printf("update x %d %d\n", l, r);
        if (!k) k=new node();
        updatey(0, nx, k->t, y, vl);
        if (l==r) return k->vl=value(k->t), void();
        int md=(l+r)/2;
        if (x<=md) updatex(l, md, k->l, x, y, vl);
        else updatex(md+1, r, k->r, x, y, vl);
        k->vl=gcd2(value(k->l), value(k->r));
    }
    ll queryy(int l, int r, pnode &k, int ql, int qr)
    {
        if (r<ql||qr<l||!k) return 0;
        if (ql<=l&&r<=qr) return k->vl;
        int md=(l+r)/2;
        return gcd2(queryy(l, md, k->l, ql, qr), queryy(md+1, r, k->r, ql, qr));
    }
    ll queryx(int l, int r, pnode &k, int ql, int a, int qr, int b)
    {
        if (r<ql||qr<l||!k) return 0;
        if (ql<=l&&r<=qr) return queryy(0, nx, k->t, a, b);
        int md=(l+r)/2;
        return gcd2(queryx(l, md, k->l, ql, a, qr, b), queryx(md+1, r, k->r, ql, a, qr, b));
    }
} s;

void init(int R, int C) {
}

void update(int P, int Q, long long K) {
    s.updatex(0, nx, s.rt, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return s.queryx(0, nx, s.rt, P, Q, U, V);
}

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