oj.uz

Submission #396504

# Submission time Handle Problem Language Result Execution time Memory
396504 2021-04-30T05:02:24 Z phathnv Game (IOI13_game) C++11
63 / 100
 2589 ms 256004 KB 
#include <bits/stdc++.h>
#include "game.h"

typedef long long ll;

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Node{
    int l, r;
    ll data;
    Node *Left, *Right;
    Node(int _l, int _r){
        l = _l;
        r = _r;
        data = 0;
        Left = Right = nullptr;
    }
    ll get(int u, int v){
        if (v < l || r < u || data == 0)
            return 0;
        if (u <= l && r <= v)
            return data;
        ll res = 0;
        if (Left != nullptr)
            res = gcd2(res, Left->get(u, v));
        if (Right != nullptr)
            res = gcd2(res, Right->get(u, v));
        return res;
    }
    void update(int pos, ll val){
        if (pos < l || r < pos)
            return;
        if (l == r){
            data = val;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid){
            if (Left == nullptr)
                Left = new Node(l, mid);
            Left->update(pos, val);
        } else {
            if (Right == nullptr)
                Right = new Node(mid + 1, r);
            Right->update(pos, val);
        }
        data = 0;
        if (Left != nullptr)
            data = gcd2(data, Left->data);
        if (Right != nullptr)
            data = gcd2(data, Right->data);
    }
};

struct Node2{
    int l, r;
    Node *data;
    Node2 *Left, *Right;
    Node2(int _l, int _r){
        l = _l;
        r = _r;
        data = new Node(0, 1e9);
        Left = Right = nullptr;
    }
    ll get(int x, int y, int u, int v){
        if (y < l || r < x || data->data == 0)
            return 0;
        if (x <= l && r <= y)
            return data->get(u, v);
        ll res = 0;
        if (Left != nullptr)
            res = gcd2(res, Left->get(x, y, u, v));
        if (Right != nullptr)
            res = gcd2(res, Right->get(x, y, u, v));
        return res;
    }
    void update(int x, int y, ll val){
        if (x < l || r < x)
            return;
        if (l == r){
            data->update(y, val);
            return;
        }
        int mid = (l + r) >> 1;
        if (Left == nullptr)
            Left = new Node2(l, mid);
        Left->update(x, y, val);
        if (Right == nullptr)
            Right = new Node2(mid + 1, r);
        Right->update(x, y, val);
        data->update(y, gcd2(Left->data->get(y, y), Right->data->get(y, y)));
    }
};

Node2 *st;

void init(int r, int c) {
    st = new Node2(0, 1e9);
}

void update(int p, int q, long long k) {
    st->update(p, q, k);
}

long long calculate(int x, int y, int u, int v) {
    return st->get(x, u, y, v);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1083 ms 73604 KB Output is correct
5 Correct 879 ms 73744 KB Output is correct
6 Correct 1098 ms 70972 KB Output is correct
7 Correct 1111 ms 70584 KB Output is correct
8 Correct 771 ms 42672 KB Output is correct
9 Correct 1118 ms 71168 KB Output is correct
10 Correct 1121 ms 70488 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1512 ms 26144 KB Output is correct
13 Correct 1968 ms 13128 KB Output is correct
14 Correct 738 ms 1552 KB Output is correct
15 Correct 2288 ms 19916 KB Output is correct
16 Correct 777 ms 34808 KB Output is correct
17 Correct 1645 ms 23704 KB Output is correct
18 Correct 2589 ms 35096 KB Output is correct
19 Correct 2280 ms 35436 KB Output is correct
20 Correct 2182 ms 34556 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 3 ms 804 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 424 KB Output is correct
12 Correct 1077 ms 73664 KB Output is correct
13 Correct 851 ms 73564 KB Output is correct
14 Correct 1138 ms 70800 KB Output is correct
15 Correct 1128 ms 70540 KB Output is correct
16 Correct 838 ms 42744 KB Output is correct
17 Correct 1150 ms 71108 KB Output is correct
18 Correct 1158 ms 70636 KB Output is correct
19 Correct 1489 ms 26304 KB Output is correct
20 Correct 1829 ms 13204 KB Output is correct
21 Correct 645 ms 1672 KB Output is correct
22 Correct 2065 ms 20256 KB Output is correct
23 Correct 724 ms 34744 KB Output is correct
24 Correct 1633 ms 23828 KB Output is correct
25 Correct 2515 ms 35084 KB Output is correct
26 Correct 2306 ms 35196 KB Output is correct
27 Correct 2213 ms 34576 KB Output is correct
28 Runtime error 683 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 844 KB Output is correct
3 Correct 3 ms 844 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 844 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 716 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 460 KB Output is correct
12 Correct 1120 ms 73328 KB Output is correct
13 Correct 851 ms 73364 KB Output is correct
14 Correct 1074 ms 70568 KB Output is correct
15 Correct 1125 ms 70452 KB Output is correct
16 Correct 742 ms 42160 KB Output is correct
17 Correct 1186 ms 70628 KB Output is correct
18 Correct 1088 ms 70124 KB Output is correct
19 Correct 1454 ms 25796 KB Output is correct
20 Correct 1841 ms 12864 KB Output is correct
21 Correct 646 ms 1340 KB Output is correct
22 Correct 2032 ms 19892 KB Output is correct
23 Correct 701 ms 34608 KB Output is correct
24 Correct 1502 ms 23492 KB Output is correct
25 Correct 2467 ms 34884 KB Output is correct
26 Correct 2135 ms 34884 KB Output is correct
27 Correct 2087 ms 34260 KB Output is correct
28 Runtime error 682 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -