oj.uz

Submission #1090381

# Submission time Handle Problem Language Result Execution time Memory
1090381 2024-09-18T09:58:56 Z vjudge1 Game (IOI13_game) C++14
37 / 100
 13000 ms 24500 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y)
{
    if (!X)
        return Y;
    ll an = __builtin_ctzll(X | Y);
    X >>= __builtin_ctzll(X);
    Y >>= __builtin_ctzll(Y);
    while (Y)
    {
        if (X > Y)
            swap(X, Y);
        Y -= X;
        Y >>= __builtin_ctzll(Y);
    }
    return X << an;
}
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 348 KB Output is correct
3 Correct 1 ms 444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 436 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 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 440 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1088 ms 21584 KB Output is correct
5 Correct 666 ms 21440 KB Output is correct
6 Correct 770 ms 23700 KB Output is correct
7 Correct 937 ms 23348 KB Output is correct
8 Correct 525 ms 15548 KB Output is correct
9 Correct 859 ms 23476 KB Output is correct
10 Correct 806 ms 23056 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 436 KB Output is correct
6 Correct 1 ms 344 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 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 5418 ms 14360 KB Output is correct
13 Execution timed out 13036 ms 6856 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 440 KB Output is correct
2 Correct 1 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 1 ms 436 KB Output is correct
7 Correct 1 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 440 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1000 ms 21720 KB Output is correct
13 Correct 636 ms 21348 KB Output is correct
14 Correct 729 ms 23732 KB Output is correct
15 Correct 838 ms 23476 KB Output is correct
16 Correct 520 ms 15600 KB Output is correct
17 Correct 812 ms 23528 KB Output is correct
18 Correct 804 ms 23220 KB Output is correct
19 Correct 5387 ms 13920 KB Output is correct
20 Execution timed out 13002 ms 6720 KB Time limit exceeded
21 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 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 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 0 ms 348 KB Output is correct
12 Correct 1076 ms 22104 KB Output is correct
13 Correct 592 ms 21952 KB Output is correct
14 Correct 686 ms 24500 KB Output is correct
15 Correct 852 ms 24088 KB Output is correct
16 Correct 507 ms 16104 KB Output is correct
17 Correct 788 ms 24248 KB Output is correct
18 Correct 768 ms 23992 KB Output is correct
19 Correct 5397 ms 14336 KB Output is correct
20 Execution timed out 13097 ms 6860 KB Time limit exceeded
21 Halted 0 ms 0 KB -