oj.uz

Submission #376222

# Submission time Handle Problem Language Result Execution time Memory
376222 2021-03-11T04:44:22 Z wind_reaper Game (IOI13_game) C++17
10 / 100
 13000 ms 10348 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

struct QuadTree{
    struct Node{
        int64_t val;
        Node *top_left, *top_right, *bottom_left, *bottom_right;
        
        Node() : top_right(0), top_left(0), bottom_right(0), bottom_left(0) {
            val = 0;
        }
    }; 

    deque<Node> tree;
    Node *root;

    Node* new_node(){
        tree.emplace_back();
        return &tree.back();
    }

    int R, C;

    void init(int _R, int _C){
        root = new_node();
        int D = max(_R, _C);
        R = 1;
        while(R < D)
            R <<= 1;
        C = R;
    }

    void update(int P, int Q, int64_t val, Node* &node, int left, int right, int top, int bottom){
        if(!node) node = new_node();
        if(bottom - top == 1 && right - left == 1){
            node->val = val;
            return;
        }

        int midR = (top + bottom) >> 1, midC = (left + right) >> 1;

        if(P < midR){
            if(Q < midC)
                update(P, Q, val, node->top_left, left, midC, top, midR);
            else update(P, Q, val, node->top_right, midC, right, top, midR);
        }
        else{
            if(Q < midC)
                update(P, Q, val, node->bottom_left, left, midC, midR, bottom);
            else update(P, Q, val, node->bottom_right, midC, right, midR, bottom);
        }
        
        node->val = 0;
        if(node->top_left) node->val = gcd(node->val, node->top_left->val);
        if(node->top_right) node->val = gcd(node->val, node->top_right->val);
        if(node->bottom_right) node->val = gcd(node->val, node->bottom_right->val);
        if(node->bottom_left) node->val = gcd(node->val, node->bottom_left->val);
    }

    int64_t query(int P, int Q, int U, int V, Node* &node, int left, int right, int top, int bottom){
        if(P >= bottom || U <= top || Q >= right || V <= left || !node)
            return 0;
        if(P <= top && U >= bottom && Q <= left && V >= right)
            return node->val;

        int midR = (top + bottom) >> 1, midC = (left + right) >> 1;

        return gcd(gcd(query(P, Q, U, V, node->top_left, left, midC, top, midR), 
                   query(P, Q, U, V, node->top_right, midC, right, top, midR)),
                   gcd(query(P, Q, U, V, node->bottom_left, left, midC, midR, bottom),
                   query(P, Q, U, V, node->bottom_right, midC, right, midR, bottom)));
    }

    void update(int P, int Q, int64_t val){
        update(P, Q, val, root, 0, C, 0, R);
    }

    int64_t query(int P, int Q, int U, int V){
        return query(P, Q, U, V, root, 0, C, 0, R);
    }
};

QuadTree T;
void init(int R, int C) {
    T.init(R, C);
}

void update(int P, int Q, long long K) {
    T.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return T.query(P, Q, U+1, V+1);
}

Compilation message

game.cpp: In constructor 'QuadTree::Node::Node()':
game.cpp:9:26: warning: 'QuadTree::Node::top_right' will be initialized after [-Wreorder]
    9 |         Node *top_left, *top_right, *bottom_left, *bottom_right;
      |                          ^~~~~~~~~
game.cpp:9:15: warning:   'QuadTree::Node* QuadTree::Node::top_left' [-Wreorder]
    9 |         Node *top_left, *top_right, *bottom_left, *bottom_right;
      |               ^~~~~~~~
game.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         Node() : top_right(0), top_left(0), bottom_right(0), bottom_left(0) {
      |         ^~~~
game.cpp:9:52: warning: 'QuadTree::Node::bottom_right' will be initialized after [-Wreorder]
    9 |         Node *top_left, *top_right, *bottom_left, *bottom_right;
      |                                                    ^~~~~~~~~~~~
game.cpp:9:38: warning:   'QuadTree::Node* QuadTree::Node::bottom_left' [-Wreorder]
    9 |         Node *top_left, *top_right, *bottom_left, *bottom_right;
      |                                      ^~~~~~~~~~~
game.cpp:11:9: warning:   when initialized here [-Wreorder]
   11 |         Node() : top_right(0), top_left(0), bottom_right(0), bottom_left(0) {
      |         ^~~~

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 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 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 13066 ms 3740 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 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 6618 ms 10348 KB Output is correct
13 Execution timed out 13083 ms 4192 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 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Execution timed out 13047 ms 3584 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 13081 ms 3400 KB Time limit exceeded
13 Halted 0 ms 0 KB -