oj.uz

Submission #225717

# Submission time Handle Problem Language Result Execution time Memory
225717 2020-04-21T11:47:40 Z johutha Game (IOI13_game) C++17
63 / 100
 2858 ms 256004 KB 
#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include <array>
#include "game.h"

#define int long long

using namespace std;

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct node1d;

using n1ptr = node1d*;

struct node1d
{
    n1ptr l = 0, r = 0;
    int v = 0;

    int query(int ql, int qr, int tl, int tr)
    {
        if (ql <= tl && tr <= qr) return v;
        if (tr < ql || qr < tl) return 0;
        if (!l) l = new node1d();
        if (!r) r = new node1d();
        return gcd(l->query(ql, qr, tl, (tl + tr)/2), r->query(ql, qr, (tl + tr)/2 + 1, tr));
    }

    void update(int k, int iv, int tl, int tr)
    {
        if (tl == tr) { v = iv; return; }
        if (!l) l = new node1d();
        if (!r) r = new node1d();
        if (k <= (tl + tr)/2) l->update(k, iv, tl, (tl + tr)/2);
        else r->update(k, iv, (tl + tr)/2 + 1, tr);
        v = gcd(l->v, r->v);
    }
};

struct node2d;

using n2ptr = node2d*;

struct node2d
{
    int w;
    n2ptr l = 0, r = 0;
    n1ptr rt;

    node2d(int iw) : w(iw), rt(new node1d()) {}

    int query(int ql, int qr, int xl, int xr, int tl, int tr)
    {
        if (ql <= tl && tr <= qr) return rt->query(xl, xr, 0, w - 1);
        if (qr < tl || tr < ql) return 0;
        if (!l) l = new node2d(w);
        if (!r) r = new node2d(w);
        return gcd(l->query(ql, qr, xl, xr, tl, (tl + tr)/2), r->query(ql, qr, xl, xr, (tl + tr)/2 + 1, tr));
    }

    void update(int ky, int kx, int iv, int tl, int tr)
    {
        if (tl == tr)
        {
            rt->update(kx, iv, 0, w - 1);
            return;
        }
        if (!l) l = new node2d(w);
        if (!r) r = new node2d(w);
        if (ky <= (tl + tr)/2) l->update(ky, kx, iv, tl, (tl + tr)/2);
        else r->update(ky, kx, iv, (tl + tr)/2 + 1, tr);
        int res = gcd(l->rt->query(kx, kx, 0, w - 1), r->rt->query(kx, kx, 0, w - 1));
        rt->update(kx, res, 0, w - 1);
    }
};

n2ptr rt;
int w, h;

void init(signed R, signed C)
{
    w = C;
    h = R;
    rt = new node2d(w);
}

void print()
{
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cout << rt->query(i, i, j, j, 0, h - 1) << " ";
        }
        cout << "\n";
    }
    cout << "\n";
}

void update(signed P, signed Q, int K)
{
    rt->update(P, Q, K, 0, h - 1);
    // print();
}

int calculate(signed P, signed Q, signed U, signed V)
{
    int res = rt->query(P, U, Q, V, 0, h - 1);
    return res;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 798 ms 36728 KB Output is correct
5 Correct 518 ms 30712 KB Output is correct
6 Correct 988 ms 79096 KB Output is correct
7 Correct 1018 ms 78840 KB Output is correct
8 Correct 863 ms 76664 KB Output is correct
9 Correct 988 ms 79864 KB Output is correct
10 Correct 950 ms 78480 KB Output is correct
11 Correct 4 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 923 ms 36860 KB Output is correct
13 Correct 1164 ms 15864 KB Output is correct
14 Correct 677 ms 6780 KB Output is correct
15 Correct 1372 ms 23508 KB Output is correct
16 Correct 328 ms 51516 KB Output is correct
17 Correct 2498 ms 215200 KB Output is correct
18 Correct 2858 ms 225748 KB Output is correct
19 Correct 2857 ms 225656 KB Output is correct
20 Correct 2782 ms 224748 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 5 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 819 ms 36600 KB Output is correct
13 Correct 515 ms 30648 KB Output is correct
14 Correct 1000 ms 79096 KB Output is correct
15 Correct 1014 ms 78968 KB Output is correct
16 Correct 861 ms 76664 KB Output is correct
17 Correct 995 ms 79788 KB Output is correct
18 Correct 939 ms 78584 KB Output is correct
19 Correct 928 ms 36984 KB Output is correct
20 Correct 1173 ms 15924 KB Output is correct
21 Correct 680 ms 6776 KB Output is correct
22 Correct 1352 ms 23544 KB Output is correct
23 Correct 316 ms 51448 KB Output is correct
24 Correct 2536 ms 215216 KB Output is correct
25 Correct 2856 ms 225624 KB Output is correct
26 Correct 2799 ms 225496 KB Output is correct
27 Correct 2769 ms 224864 KB Output is correct
28 Runtime error 395 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 6 ms 640 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 640 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 5 ms 512 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 801 ms 36728 KB Output is correct
13 Correct 500 ms 30712 KB Output is correct
14 Correct 991 ms 79096 KB Output is correct
15 Correct 1018 ms 78840 KB Output is correct
16 Correct 866 ms 76664 KB Output is correct
17 Correct 1042 ms 79860 KB Output is correct
18 Correct 941 ms 78712 KB Output is correct
19 Correct 923 ms 36984 KB Output is correct
20 Correct 1169 ms 15848 KB Output is correct
21 Correct 665 ms 6904 KB Output is correct
22 Correct 1343 ms 23440 KB Output is correct
23 Correct 316 ms 51488 KB Output is correct
24 Correct 2506 ms 215288 KB Output is correct
25 Correct 2856 ms 225616 KB Output is correct
26 Correct 2825 ms 225524 KB Output is correct
27 Correct 2799 ms 224748 KB Output is correct
28 Runtime error 393 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -