oj.uz

Submission #1090347

# Submission time Handle Problem Language Result Execution time Memory
1090347 2024-09-18T09:22:21 Z vjudge1 Game (IOI13_game) C++14
0 / 100
 1 ms 440 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y)
{
    ll tmp;
    while (X != Y && Y != 0)
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
ll t = 1;
vector<ll> sg = {0};
vector<int> pa = {0}, ctl = {-1}, ctr = {-1}, cbl = {-1}, cbr = {-1}, wl = {0}, wr = {0}, wt = {0}, wb = {0};
void cre(int i, int x)
{
    sg.push_back(0);
    pa.push_back(i);
    ctl.push_back(-1);
    ctr.push_back(-1);
    cbl.push_back(-1);
    cbr.push_back(-1);
    ll md = ((wl[i] + wr[i]) >> 1);
    if (x & 1)
    {
        wl.push_back(md);
        wr.push_back(wr[i]);
    }
    else
    {
        wl.push_back(wl[i]);
        wr.push_back(md);
    }
    md = ((wt[i] + wb[i]) >> 1);
    if (x & 2)
    {
        wt.push_back(md);
        wb.push_back(wb[i]);
    }
    else
    {
        wt.push_back(wt[i]);
        wb.push_back(md);
    }
    if (!x)
        ctl[i] = t;
    else if (x == 1)
        ctr[i] = t;
    else if (x == 2)
        cbl[i] = t;
    else
        cbr[i] = t;
    t++;
}
void upd(int a, int b, int i, int x)
{
    if (wt[i] > a || wb[i] <= a || wl[i] > b || wr[i] <= b)
        return;
    if (wt[i] == a && wb[i] == a + 1 && wl[i] == b && wr[i] == b + 1)
    {
        sg[i] = x;
        return;
    }
    if (ctl[i] == -1)
        cre(i, 0);
    upd(a, b, ctl[i], x);
    if (ctr[i] == -1)
        cre(i, 1);
    upd(a, b, ctr[i], x);
    if (cbl[i] == -1)
        cre(i, 2);
    upd(a, b, cbl[i], x);
    if (cbr[i] == -1)
        cre(i, 3);
    upd(a, b, cbr[i], x);
    sg[i] = gcd2(gcd2(sg[ctl[i]], sg[ctr[i]]), gcd2(sg[cbl[i]], sg[cbr[i]]));
}
ll qu(int t, int b, int l, int r, int i)
{
    if (wt[i] >= b || wb[i] <= t || wl[i] >= r || wr[i] <= l)
        return 0;
    if (wt[i] >= t && wb[i] <= b && wl[i] >= l && wr[i] <= r)
        return sg[i];
    ll an = 0;
    if (ctl[i] != -1)
        an = gcd2(an, qu(t, b, l, r, ctl[i]));
    if (ctr[i] != -1)
        an = gcd2(an, qu(t, b, l, r, ctr[i]));
    if (cbl[i] != -1)
        an = gcd2(an, qu(t, b, l, r, cbl[i]));
    if (cbr[i] != -1)
        an = gcd2(an, qu(t, b, l, r, cbr[i]));
    return an;
}
void init(int R, int C)
{
    wr[0] = C;
    wb[0] = R;
}
void update(int P, int Q, ll K)
{
    upd(P, Q, 0, K);
}
ll calculate(int P, int Q, int U, int V)
{
    return qu(P, U + 1, Q, V + 1, 0);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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