oj.uz

Submission #225719

# Submission time Handle Problem Language Result Execution time Memory
225719 2020-04-21T11:51:52 Z johutha Game (IOI13_game) C++14
63 / 100
 1690 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 && !r) 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 && !r) 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 4 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 624 ms 21496 KB Output is correct
5 Correct 419 ms 21752 KB Output is correct
6 Correct 574 ms 18740 KB Output is correct
7 Correct 656 ms 18560 KB Output is correct
8 Correct 446 ms 13304 KB Output is correct
9 Correct 637 ms 18684 KB Output is correct
10 Correct 589 ms 18168 KB Output is correct
11 Correct 5 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 5 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 4 ms 256 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 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 898 ms 25720 KB Output is correct
13 Correct 1214 ms 11896 KB Output is correct
14 Correct 361 ms 4088 KB Output is correct
15 Correct 1439 ms 16248 KB Output is correct
16 Correct 296 ms 32760 KB Output is correct
17 Correct 1002 ms 20600 KB Output is correct
18 Correct 1690 ms 31628 KB Output is correct
19 Correct 1446 ms 32120 KB Output is correct
20 Correct 1362 ms 31464 KB Output is correct
21 Correct 5 ms 384 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 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 630 ms 20056 KB Output is correct
13 Correct 425 ms 20476 KB Output is correct
14 Correct 604 ms 17528 KB Output is correct
15 Correct 707 ms 17272 KB Output is correct
16 Correct 482 ms 11928 KB Output is correct
17 Correct 666 ms 17428 KB Output is correct
18 Correct 621 ms 16952 KB Output is correct
19 Correct 925 ms 24476 KB Output is correct
20 Correct 1224 ms 10616 KB Output is correct
21 Correct 349 ms 2808 KB Output is correct
22 Correct 1447 ms 14928 KB Output is correct
23 Correct 284 ms 31352 KB Output is correct
24 Correct 1008 ms 19708 KB Output is correct
25 Correct 1682 ms 31124 KB Output is correct
26 Correct 1420 ms 31224 KB Output is correct
27 Correct 1362 ms 30568 KB Output is correct
28 Runtime error 631 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 384 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 5 ms 256 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 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 614 ms 19576 KB Output is correct
13 Correct 437 ms 20216 KB Output is correct
14 Correct 592 ms 17020 KB Output is correct
15 Correct 664 ms 16760 KB Output is correct
16 Correct 438 ms 11512 KB Output is correct
17 Correct 618 ms 17272 KB Output is correct
18 Correct 585 ms 16604 KB Output is correct
19 Correct 872 ms 23800 KB Output is correct
20 Correct 1215 ms 10016 KB Output is correct
21 Correct 361 ms 2300 KB Output is correct
22 Correct 1421 ms 14456 KB Output is correct
23 Correct 297 ms 30984 KB Output is correct
24 Correct 1004 ms 19832 KB Output is correct
25 Correct 1678 ms 31096 KB Output is correct
26 Correct 1435 ms 31224 KB Output is correct
27 Correct 1357 ms 30328 KB Output is correct
28 Runtime error 635 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -