oj.uz

Submission #376223

# Submission time Handle Problem Language Result Execution time Memory
376223 2021-03-11T04:51:48 Z wind_reaper Game (IOI13_game) C++17
37 / 100
 13000 ms 11984 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_left(0), top_right(0), bottom_left(0), bottom_right(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();
        this->R = _R;
        this->C = _C;
    }

    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);
}

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 384 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 0 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1336 ms 10860 KB Output is correct
5 Correct 964 ms 11984 KB Output is correct
6 Correct 842 ms 9356 KB Output is correct
7 Correct 947 ms 8952 KB Output is correct
8 Correct 615 ms 8172 KB Output is correct
9 Correct 942 ms 9324 KB Output is correct
10 Correct 942 ms 8772 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

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 6675 ms 6368 KB Output is correct
13 Execution timed out 13080 ms 1876 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 Correct 1365 ms 10604 KB Output is correct
13 Correct 951 ms 11756 KB Output is correct
14 Correct 839 ms 9632 KB Output is correct
15 Correct 1006 ms 9104 KB Output is correct
16 Correct 635 ms 7916 KB Output is correct
17 Correct 921 ms 9196 KB Output is correct
18 Correct 885 ms 8700 KB Output is correct
19 Correct 6617 ms 10284 KB Output is correct
20 Execution timed out 13020 ms 4704 KB Time limit exceeded
21 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 Correct 1338 ms 10752 KB Output is correct
13 Correct 959 ms 11872 KB Output is correct
14 Correct 842 ms 9324 KB Output is correct
15 Correct 993 ms 9140 KB Output is correct
16 Correct 618 ms 7944 KB Output is correct
17 Correct 1002 ms 9176 KB Output is correct
18 Correct 907 ms 8812 KB Output is correct
19 Correct 6550 ms 10512 KB Output is correct
20 Execution timed out 13063 ms 4132 KB Time limit exceeded
21 Halted 0 ms 0 KB -