oj.uz

Submission #384034

# Submission time Handle Problem Language Result Execution time Memory
384034 2021-03-31T08:31:38 Z ParsaAlizadeh Game (IOI13_game) C++17
10 / 100
 13000 ms 12456 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
 
typedef long long       ll;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;
 
#define all(x)          x.begin(), x.end()
#define kill(x)         return cout << x << endl, 0
#define X               first
#define Y               second
#define endl            '\n'

inline ll gcd2(register ll x, register ll y) {
    register ll tmp;
    while (x != y && y != 0) {
        tmp = x;
        x = y;
        y = tmp % y;
    }
    return x;
}
 
struct Tree {
    ll data;
    pii A, B;
    Tree *ul, *ur, *dl, *dr;
 
    Tree(const pii & _A, const pii & _B) : data(0), A(_A), B(_B) {}
 
    ll push(int x, int y, ll val) {
        if (x < A.X || y < A.Y || x >= B.X || y >= B.Y)
            return data;
        if (A.X + 1 == B.X) {
            return data = val;
        }
        if (ul == nullptr) {
            pii mid = {(A.X + B.X) >> 1, (A.Y + B.Y) >> 1};
            ul = new Tree({A.X, A.Y}, {mid.X, mid.Y});
            ur = new Tree({A.X, mid.Y}, {mid.X, B.Y});
            dl = new Tree({mid.X, A.Y}, {B.X, mid.Y});
            dr = new Tree({mid.X, mid.Y}, {B.X, B.Y});
        }
        data = ul->push(x, y, val);
        data = gcd2(data, ur->push(x, y, val));
        data = gcd2(data, dl->push(x, y, val));
        data = gcd2(data, dr->push(x, y, val));
        return data;
    }
 
    ll query(const pii & C, const pii & D, ll res) {
        if (data == 0 || D.X <= A.X || D.Y <= A.Y || B.X <= C.X || B.Y <= C.Y)
            return res;
        if (C.X <= A.X && C.Y <= A.Y && B.X <= D.X && B.Y <= D.Y)
            return gcd2(data, res);
        res = ul->query(C, D, res);
        res = ur->query(C, D, res);
        res = dl->query(C, D, res);
        res = dr->query(C, D, res);
        return res;
    }
} *root;
 
void init(int R, int C) {
    int n = 1;
    while (n < R || n < C) {
        n <<= 1;
    }
    root = new Tree({0, 0}, {n, n});
}
 
void update(int P, int Q, ll K) {
    root->push(P, Q, K);
}
 
ll calculate(int P, int Q, int U, int V) {
    return root->query({P, Q}, {U + 1, V + 1}, 0);
}

Compilation message

game.cpp:15:28: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   15 | inline ll gcd2(register ll x, register ll y) {
      |                            ^
game.cpp:15:43: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   15 | inline ll gcd2(register ll x, register ll y) {
      |                                           ^
game.cpp: In function 'll gcd2(ll, ll)':
game.cpp:16:17: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   16 |     register ll tmp;
      |                 ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Execution timed out 13056 ms 5892 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 5246 ms 12456 KB Output is correct
13 Execution timed out 13003 ms 4684 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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Execution timed out 13021 ms 6040 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Execution timed out 13092 ms 6320 KB Time limit exceeded
13 Halted 0 ms 0 KB -