oj.uz

Submission #376035

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

using namespace std;

/*struct SegmentTree{
    struct Node{
        int64_t val;
        Node *lc, *rc;

        Node() : val(0), lc(0), rc(0) {}
    };
    
    vector<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(r - l == 1){
            if(!node) node = new_node();
            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(l >= lx && r <= rx)
            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);
    }
};*/

struct SegmentTree{
    vector<int64_t> st;
    int sz = 1;
    void init(int n){
        while(sz < n)
            sz <<= 1; 
        st.resize(2*sz, 0); 
    }

    void update(int i, int64_t v, int x, int lx, int rx){
        if(rx - lx == 1){
            st[x] = v; 
            return; 
        }

        int mid = (lx + rx) >> 1; 

        if(mid > i)
            update(i, v, 2*x+1, lx, mid); 
        else 
            update(i, v, 2*x+2, mid, rx);

        st[x] = __gcd(st[2*x+1], st[2*x+2]);  
    }

    void update(int i, int64_t v){
        update(i, v, 0, 0, sz); 
    }

    int64_t query(int l, int r, int x, int lx, int rx){
        if(lx >= r || rx <= l)
            return 0; 
        if(lx >= l && rx <= r)
            return st[x]; 

        int mid = (lx + rx) >> 1;

        return __gcd(query(l, r, 2*x+1, lx, mid), query(l, r, 2*x+2, mid, rx)); 
    }

    int64_t query(int l, int r){
        return query(l, r, 0, 0, sz); 
    }
}; 
vector<SegmentTree> T;

void init(int R, int C) {
    T.resize(R);
    for(int i = 0; i < R; i++){
        T[i].init(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 364 KB Output is correct
2 Correct 1 ms 492 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 492 KB Output is correct
6 Correct 1 ms 492 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 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 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 929 ms 25868 KB Output is correct
5 Correct 502 ms 28908 KB Output is correct
6 Correct 827 ms 25324 KB Output is correct
7 Correct 758 ms 25084 KB Output is correct
8 Correct 670 ms 25836 KB Output is correct
9 Correct 779 ms 25452 KB Output is correct
10 Correct 678 ms 25068 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 492 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 492 KB Output is correct
6 Correct 1 ms 492 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Execution timed out 13096 ms 18724 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 492 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 492 KB Output is correct
6 Correct 1 ms 492 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 845 ms 25980 KB Output is correct
13 Correct 503 ms 27756 KB Output is correct
14 Correct 752 ms 25696 KB Output is correct
15 Correct 767 ms 25324 KB Output is correct
16 Correct 662 ms 25580 KB Output is correct
17 Correct 742 ms 25452 KB Output is correct
18 Correct 702 ms 24780 KB Output is correct
19 Execution timed out 13088 ms 19728 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 492 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 492 KB Output is correct
6 Correct 1 ms 640 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 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 841 ms 26440 KB Output is correct
13 Correct 502 ms 28268 KB Output is correct
14 Correct 760 ms 25512 KB Output is correct
15 Correct 747 ms 24300 KB Output is correct
16 Correct 669 ms 25380 KB Output is correct
17 Correct 765 ms 24428 KB Output is correct
18 Correct 670 ms 23660 KB Output is correct
19 Execution timed out 13008 ms 19848 KB Time limit exceeded
20 Halted 0 ms 0 KB -