oj.uz

Submission #225724

# Submission time Handle Problem Language Result Execution time Memory
225724 2020-04-21T11:56:43 Z johutha Game (IOI13_game) C++17
0 / 100
 13000 ms 384 KB 
#include <iostream>
#include <vector>
#include <memory>
#include <random>
#include <array>
#include "game.h"

using namespace std;

long long gcd(long long a, long long 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;
    long long v = 0;

    long long 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, long long 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()) {}

    long long 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, long long 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, long long K)
{
    rt->update(P, Q, K, 0, h - 1);
    // print();
}

long long calculate(signed P, signed Q, signed U, signed V)
{
    long long 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 13049 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
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 Execution timed out 13078 ms 384 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 13083 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Execution timed out 13093 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Execution timed out 13045 ms 256 KB Time limit exceeded
3 Halted 0 ms 0 KB -