oj.uz

Submission #396509

# Submission time Handle Problem Language Result Execution time Memory
396509 2021-04-30T05:19:19 Z phathnv Game (IOI13_game) C++11
63 / 100
 2496 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 (x <= mid){
            if (Left == nullptr)
                Left = new Node2(l, mid);
            Left->update(x, y, val);
        } else {
            if (Right == nullptr)
                Right = new Node2(mid + 1, r);
            Right->update(x, y, val);
        }
        ll newVal = 0;
        if (Left != nullptr)
            newVal = gcd2(newVal, Left->data->get(y, y));
        if (Right != nullptr)
            newVal = gcd2(newVal, Right->data->get(y, y));
        data->update(y, newVal);
    }
};

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) {
    assert(x <= u && y <= 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 716 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 720 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 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 1064 ms 73188 KB Output is correct
5 Correct 827 ms 73164 KB Output is correct
6 Correct 1040 ms 70432 KB Output is correct
7 Correct 1082 ms 70176 KB Output is correct
8 Correct 714 ms 42228 KB Output is correct
9 Correct 1107 ms 70672 KB Output is correct
10 Correct 1037 ms 70120 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 716 KB Output is correct
3 Correct 4 ms 716 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 716 KB Output is correct
7 Correct 1 ms 336 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 1395 ms 25952 KB Output is correct
13 Correct 1753 ms 12948 KB Output is correct
14 Correct 620 ms 1348 KB Output is correct
15 Correct 1966 ms 19652 KB Output is correct
16 Correct 661 ms 34456 KB Output is correct
17 Correct 1470 ms 23620 KB Output is correct
18 Correct 2463 ms 34696 KB Output is correct
19 Correct 2137 ms 34928 KB Output is correct
20 Correct 2113 ms 34352 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 332 KB Output is correct
2 Correct 3 ms 828 KB Output is correct
3 Correct 3 ms 820 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 716 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 1031 ms 73196 KB Output is correct
13 Correct 801 ms 73156 KB Output is correct
14 Correct 1048 ms 70576 KB Output is correct
15 Correct 1086 ms 70204 KB Output is correct
16 Correct 716 ms 42368 KB Output is correct
17 Correct 1108 ms 70596 KB Output is correct
18 Correct 1050 ms 70224 KB Output is correct
19 Correct 1381 ms 25796 KB Output is correct
20 Correct 1746 ms 12996 KB Output is correct
21 Correct 623 ms 1288 KB Output is correct
22 Correct 2005 ms 19868 KB Output is correct
23 Correct 661 ms 34420 KB Output is correct
24 Correct 1501 ms 23480 KB Output is correct
25 Correct 2418 ms 34780 KB Output is correct
26 Correct 2248 ms 34920 KB Output is correct
27 Correct 2080 ms 34460 KB Output is correct
28 Runtime error 718 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 716 KB Output is correct
3 Correct 3 ms 716 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 716 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 1040 ms 73212 KB Output is correct
13 Correct 800 ms 73216 KB Output is correct
14 Correct 1100 ms 70512 KB Output is correct
15 Correct 1117 ms 70340 KB Output is correct
16 Correct 745 ms 42404 KB Output is correct
17 Correct 1080 ms 70832 KB Output is correct
18 Correct 1068 ms 70212 KB Output is correct
19 Correct 1402 ms 25680 KB Output is correct
20 Correct 1748 ms 12876 KB Output is correct
21 Correct 631 ms 1348 KB Output is correct
22 Correct 2009 ms 19756 KB Output is correct
23 Correct 668 ms 34772 KB Output is correct
24 Correct 1508 ms 23568 KB Output is correct
25 Correct 2496 ms 34712 KB Output is correct
26 Correct 2186 ms 35160 KB Output is correct
27 Correct 2076 ms 34244 KB Output is correct
28 Runtime error 689 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -