Submission #376222

#	Time	Username	Problem	Language	Result	Execution time	Memory
376222		wind_reaper	Game (IOI13_game)	C++17	10 / 100	13083 ms	10348 KiB

game

#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 (stderr)

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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20