oj.uz

Submission #1090365

# Submission time Handle Problem Language Result Execution time Memory
1090365 2024-09-18T09:33:41 Z vjudge1 Game (IOI13_game) C++14
37 / 100
 13000 ms 24604 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, ll 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 428 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 967 ms 22208 KB Output is correct
5 Correct 619 ms 22144 KB Output is correct
6 Correct 657 ms 24504 KB Output is correct
7 Correct 777 ms 24324 KB Output is correct
8 Correct 471 ms 16068 KB Output is correct
9 Correct 769 ms 24264 KB Output is correct
10 Correct 692 ms 23960 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 4964 ms 14636 KB Output is correct
13 Execution timed out 13049 ms 7112 KB Time limit exceeded
14 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 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 965 ms 22124 KB Output is correct
13 Correct 562 ms 21956 KB Output is correct
14 Correct 646 ms 24504 KB Output is correct
15 Correct 761 ms 24260 KB Output is correct
16 Correct 454 ms 16156 KB Output is correct
17 Correct 724 ms 24348 KB Output is correct
18 Correct 702 ms 23992 KB Output is correct
19 Correct 5141 ms 14528 KB Output is correct
20 Execution timed out 13069 ms 6872 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1002 ms 22208 KB Output is correct
13 Correct 605 ms 21948 KB Output is correct
14 Correct 647 ms 24604 KB Output is correct
15 Correct 764 ms 24248 KB Output is correct
16 Correct 452 ms 16060 KB Output is correct
17 Correct 734 ms 24464 KB Output is correct
18 Correct 731 ms 23788 KB Output is correct
19 Correct 5219 ms 14640 KB Output is correct
20 Execution timed out 13034 ms 7020 KB Time limit exceeded
21 Halted 0 ms 0 KB -