oj.uz

Submission #396501

# Submission time Handle Problem Language Result Execution time Memory
396501 2021-04-30T04:55:04 Z phathnv Game (IOI13_game) C++11
63 / 100
 2939 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 (Left == nullptr)
            Left = new Node(l, mid);
        Left->update(pos, val);
        if (Right == nullptr)
            Right = new Node(mid + 1, r);
        Right->update(pos, val);
        data = gcd2(Left->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 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 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 1104 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 588 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 1182 ms 114456 KB Output is correct
5 Correct 1000 ms 114276 KB Output is correct
6 Correct 1270 ms 111844 KB Output is correct
7 Correct 1268 ms 111780 KB Output is correct
8 Correct 840 ms 69060 KB Output is correct
9 Correct 1284 ms 112560 KB Output is correct
10 Correct 1273 ms 111568 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 2 ms 332 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 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 1100 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 1100 KB Output is correct
10 Correct 3 ms 800 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 1499 ms 39404 KB Output is correct
13 Correct 1976 ms 22724 KB Output is correct
14 Correct 710 ms 6284 KB Output is correct
15 Correct 2061 ms 34380 KB Output is correct
16 Correct 782 ms 59560 KB Output is correct
17 Correct 1758 ms 42476 KB Output is correct
18 Correct 2755 ms 61004 KB Output is correct
19 Correct 2484 ms 61368 KB Output is correct
20 Correct 2370 ms 60516 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 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 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 1104 KB Output is correct
7 Correct 1 ms 424 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 5 ms 1100 KB Output is correct
10 Correct 2 ms 796 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1211 ms 114484 KB Output is correct
13 Correct 975 ms 114376 KB Output is correct
14 Correct 1227 ms 111992 KB Output is correct
15 Correct 1318 ms 111640 KB Output is correct
16 Correct 820 ms 69056 KB Output is correct
17 Correct 1353 ms 112680 KB Output is correct
18 Correct 1264 ms 111680 KB Output is correct
19 Correct 1533 ms 39480 KB Output is correct
20 Correct 1798 ms 22852 KB Output is correct
21 Correct 729 ms 6220 KB Output is correct
22 Correct 2098 ms 34400 KB Output is correct
23 Correct 792 ms 59600 KB Output is correct
24 Correct 1799 ms 42440 KB Output is correct
25 Correct 2766 ms 60948 KB Output is correct
26 Correct 2615 ms 61068 KB Output is correct
27 Correct 2422 ms 60424 KB Output is correct
28 Runtime error 518 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 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 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 1060 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1232 ms 114720 KB Output is correct
13 Correct 999 ms 114608 KB Output is correct
14 Correct 1345 ms 112100 KB Output is correct
15 Correct 1450 ms 112032 KB Output is correct
16 Correct 824 ms 69276 KB Output is correct
17 Correct 1391 ms 112832 KB Output is correct
18 Correct 1289 ms 111948 KB Output is correct
19 Correct 1592 ms 39580 KB Output is correct
20 Correct 1854 ms 22684 KB Output is correct
21 Correct 687 ms 6376 KB Output is correct
22 Correct 2140 ms 34536 KB Output is correct
23 Correct 816 ms 59524 KB Output is correct
24 Correct 1839 ms 42552 KB Output is correct
25 Correct 2939 ms 61164 KB Output is correct
26 Correct 2670 ms 61156 KB Output is correct
27 Correct 2465 ms 60456 KB Output is correct
28 Runtime error 491 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -