oj.uz

Submission #1075618

# Submission time Handle Problem Language Result Execution time Memory
1075618 2024-08-26T08:00:39 Z Ignut Game (IOI13_game) C++17
0 / 100
 2 ms 1628 KB 
// Ignut

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

using namespace std;
using ll = long long;

vector<ll> t[8001];

int r, c;

void init(int R, int C) {
    r = R, c = C;
    // t.assign(4 * R, {});
    for (int i = 0; i < 2 * R; i ++) t[i].assign(2 * C, 0);
}

void Change(int ind, int v, int l, int r, int pos, ll val) {
    if (l == r) {
        t[ind][v] = val;
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid)
        Change(ind, v * 2, l, mid, pos, val);
    else
        Change(ind, v * 2 + 1, mid + 1, r, pos, val);
    t[ind][v] = gcd(t[ind][v * 2], t[ind][v * 2 + 1]);
}

void Update(int ind, int v, int l, int r, int pos, ll val) {
    t[ind][v] = gcd(t[ind * 2][v], t[ind * 2 + 1][v]);
    if (l == r) {
        return;
    }
    int mid = l + (r - l) / 2;
    if (pos <= mid)
        Update(ind, v * 2, l, mid, pos, val);
    else
        Update(ind, v * 2 + 1, mid + 1, r, pos, val);
}

void ChangeR(int v, int l, int r, int posR, int posC, ll val) {
    // cout << "update ind=" << v << '\n'; 
    if (l == r) {
        Change(v, 1, 0, c - 1, posC, val);
        return;
    }
    int mid = l + (r - l) / 2;
    if (posR <= mid)
        ChangeR(v * 2, l, mid, posR, posC, val);
    else
        ChangeR(v * 2 + 1, mid + 1, r, posR, posC, val);
    Update(v, 1, 0, c - 1, posC, val);
}

void update(int P, int Q, ll K) {
    ChangeR(1, 0, r - 1, P, Q, K);
}

ll Ask(int ind, int v, int l, int r, int ql, int qr) {
    if (ql > r || l > qr)
        return 0ll;
    if (l >= ql && r <= qr)
        return t[ind][v];
    int mid = l + (r - l) / 2;
    return gcd(Ask(ind, v * 2, l, mid, ql, qr), Ask(ind, v * 2 + 1, mid + 1, r, ql, qr));
}

ll AskR(int v, int l, int r, int ql_r, int qr_r, int ql_c, int qr_c) {
    if (l > qr_r || ql_r > r)
        return 0;
    if (l >= ql_r && r <= qr_r) {
        // cout << "ask ind=" << v << '\n';
        // cout << "get " << Ask(v, 1, 0, c - 1, ql_c, qr_c) << '\n';
        return Ask(v, 1, 0, c - 1, ql_c, qr_c);
    }
    int mid = l + (r - l) / 2;
    return gcd(AskR(v * 2, l, mid, ql_r, qr_r, ql_c, qr_c), AskR(v * 2 + 1, mid + 1, r, ql_r, qr_r, ql_c, qr_c));
}

ll calculate(int P, int Q, int U, int V) {
    // ll res = 0;
    // for (int ind = P; ind <= U; ind ++)
    //     res = gcd(res, Ask(ind, 1, 0, c - 1, Q, V));
    // return res;
    return AskR(1, 0, r - 1, P, U, Q, V);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Runtime error 2 ms 1372 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Runtime error 1 ms 860 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 2 ms 1628 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Runtime error 2 ms 1372 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Runtime error 1 ms 1372 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -