oj.uz

Submission #396493

# Submission time Handle Problem Language Result Execution time Memory
396493 2021-04-30T04:39:47 Z phathnv Game (IOI13_game) C++11
0 / 100
 1 ms 296 KB 
#include <bits/stdc++.h>
#include "game.h"

typedef long long ll;

using namespace std;

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 Node{
    int l, r;
    ll data;
    Node *Left, *Right;
    Node(int _l, int _r){
        l = _l;
        r = _r;
        data = 0;
        Left = Right = nullptr;
    }
    ll get(int u, int v){
        if (v < l || r < u || data == 0)
            return 0;
        if (u <= l && r <= v)
            return data;
        ll res = 0;
        if (Left != nullptr)
            res = gcd2(res, Left->get(u, v));
        if (Right != nullptr)
            res = gcd2(res, Right->get(u, v));
        return res;
    }
    void update(int pos, int val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            data = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (Left == nullptr)
            Left = new Node(l, mid);
        Left->update(pos, val);
        if (Right == nullptr)
            Right = new Node(mid + 1, r);
        Right->update(pos, val);
        data = gcd2(Left->data, Right->data);
    }
};

Node* root[100];

void init(int r, int c) {
    for(int i = 0; i < r; i++)
        root[i] = new Node(0, c - 1);
}

void update(int p, int q, long long k) {
    root[p]->update(q, k);
}

long long calculate(int x, int y, int u, int v) {
    ll res = 0;
    for(int i = x; i <= u; i++){
        res = gcd2(res, root[i]->get(y, v));
    }
    return res;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 296 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 204 KB Output isn't correct
2 Halted 0 ms 0 KB -