oj.uz

Submission #924902

# Submission time Handle Problem Language Result Execution time Memory
924902 2024-02-10T03:41:36 Z 12345678 Game (IOI13_game) C++17
0 / 100
 3 ms 860 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

const ll 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(ll l, ll r, pnode &k, ll y, ll vl)
    {
        if (!k) k=new node();
        if (l==r) return k->vl=vl, void();
        ll 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(ll l, ll r, pnode &k, ll x, ll y, ll vl)
    {
        if (!k) k=new node();
        updatey(0, nx, k->t, y, vl);
        if (l==r) return k->vl=value(k->t), void();
        ll 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(ll l, ll r, pnode &k, ll ql, ll qr)
    {
        if (r<ql||qr<l||!k) return 0;
        if (ql<=l&&r<=qr) return k->vl;
        ll md=(l+r)/2;
        return gcd2(queryy(l, md, k->l, ql, qr), queryy(md+1, r, k->r, ql, qr));
    }
    ll queryx(ll l, ll r, pnode &k, ll ql, ll a, ll qr, ll b)
    {
        if (r<ql||qr<l||!k) return 0;
        if (ql<=l&&r<=qr) return queryy(0, nx, k->t, a, b);
        ll 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, ll 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 2 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 3 ms 808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 2 ms 856 KB Output isn't correct
3 Halted 0 ms 0 KB -