oj.uz

Submission #376040

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

using namespace std;

struct SegmentTree{
    struct Node{
        int64_t val;
        Node *lc, *rc;
 
        Node() : lc(0), rc(0) {
            val = 0LL;
        }
    };
    
    deque<Node> tree;
 
    Node* new_node(){
        tree.emplace_back();
        return &tree.back();
    }

    Node *root;
    int L, R;

    void init(int _L, int _R){
        this->L = _L;
        this->R = _R;
        root = new_node();
    }
 
    void update(int idx, int64_t val, Node* &node, int l, int r){
        if(!node) node = new_node();
        if(r - l == 1){
            node->val = val;
            return;
        }
 
        int mid = (l + r) >> 1;
 
        if(idx < mid) update(idx, val, node->lc, l, mid);
        else update(idx, val, node->rc, mid, r);
 
        node->val = __gcd((node->lc ? node->lc->val : 0), (node->rc ? node->rc->val : 0));
    }
 
    int64_t query(int l, int r, Node* &node, int lx, int rx){
        if(r <= lx || l >= rx || !node)
            return 0;
        if(lx >= l && rx <= r)
            return node->val;
 
        int mid = (lx + rx) >> 1;
        
        return __gcd(query(l, r, node->lc, lx, mid), query(l, r, node->rc, mid, rx));
    }
 
    void update(int idx, int64_t val){
        update(idx, val, root, L, R);
    }
 
    int64_t query(int l, int r){
        return query(l, r, root, L, R);
    }
};

vector<SegmentTree> T;

void init(int R, int C) {
    T.resize(R);
    for(int i = 0; i < R; i++){
        T[i].init(0, C);
    }
}

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

long long calculate(int P, int Q, int U, int V) {
    int64_t res = 0;
    for(int i = P; i <= U; i++){
        res = __gcd(res, T[i].query(Q, V+1));
    }
    return res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 384 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 686 ms 6512 KB Output is correct
5 Correct 473 ms 6840 KB Output is correct
6 Correct 555 ms 3876 KB Output is correct
7 Correct 615 ms 3376 KB Output is correct
8 Correct 417 ms 3180 KB Output is correct
9 Correct 640 ms 3364 KB Output is correct
10 Correct 557 ms 3052 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 492 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 13009 ms 6208 KB Time limit exceeded
13 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 685 ms 6640 KB Output is correct
13 Correct 477 ms 6764 KB Output is correct
14 Correct 547 ms 3648 KB Output is correct
15 Correct 628 ms 3392 KB Output is correct
16 Correct 418 ms 3180 KB Output is correct
17 Correct 583 ms 3564 KB Output is correct
18 Correct 533 ms 3052 KB Output is correct
19 Execution timed out 13026 ms 8304 KB Time limit exceeded
20 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 691 ms 6892 KB Output is correct
13 Correct 471 ms 7164 KB Output is correct
14 Correct 541 ms 3820 KB Output is correct
15 Correct 600 ms 3852 KB Output is correct
16 Correct 413 ms 3564 KB Output is correct
17 Correct 591 ms 3820 KB Output is correct
18 Correct 518 ms 3308 KB Output is correct
19 Execution timed out 13091 ms 7768 KB Time limit exceeded
20 Halted 0 ms 0 KB -