oj.uz

Submission #363849

# Submission time Handle Problem Language Result Execution time Memory
363849 2021-02-07T11:23:56 Z Gareton Game (IOI13_game) C++
0 / 100
 205 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define orset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#pragma GCC optimize("O3")
// #pragma GCC target("sse", "sse2", "sse3", "sse4")
//#pragma GCC target("avx2")
#define int long long
#define ll long long
#define pii pair<int, int>
#define x first
#define y second
#define all(a) (a.begin()), (a.end())
#define gsz(x) ((int)x.size())
#define endl "\n"
#define LOCAL
#ifdef LOCAL
#define dbg(x) cerr << #x << ":" << (x) << endl
#define print(x) cerr << (x) << endl
#else
#define dbg(x) 0
#define print(x) 0
#endif

using namespace std;
using namespace __gnu_pbds;

const int N = 2e6 + 10;
const int B = 340;
const ll inf = 1e18 + 10;
const ll mod = 1e9 + 7;

mt19937 rnd(4);//chrono::high_resolution_clock::now().time_since_epoch().count());

long long gcd2(long long X, long long Y) {
    assert(X >= 0 && Y >= 0);

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct nodey{
    int y, prior = rnd();
    int val, gcd;
    int l = -1, r = -1;
};

struct nodex{
    int l = -1, r = -1;
    int rooty = -1;
};

nodex tx[N];
nodey ty[N];
int n, m;
int topx = 0, topy = 0;
int rootx = -1;

int getgcd(int v)
{
    return v == -1 ? 0 : ty[v].gcd;
}

void updy(int v)
{
    if(v == -1) return;

    ty[v].gcd = gcd2(gcd2(ty[v].val, getgcd(ty[v].l)), getgcd(ty[v].r));
}



int mergey(int l, int r)
{
    if(l == -1) return r;
    if(r == -1) return l;

    if(ty[l].prior > ty[r].prior)
    {
        ty[l].r = mergey(ty[l].r, r);

        updy(l);

        return l;
    }
    else
    {
        ty[r].l = mergey(l, ty[r].l);

        updy(r);

        return r;
    }
}

pii splity(int v, int k)
{
    if(v == -1) return {-1, -1};

    if(ty[v].y > k)
    {
        pii p = splity(ty[v].l, k);

        ty[v].l = p.y;
        updy(v);

        return {p.x, v};
    }
    else
    {
        pii p = splity(ty[v].r, k);

        ty[v].r = p.x;
        updy(v);

        return {v, p.y};
    }
}

int createx()
{
    int v = topx++;

    return v;
}

int stupid[5010][5010];

int gety(int &v, int ly, int ry)
{
    // pii p1 = splity(v, ly - 1);
    // pii p2 = splity(p1.y, ry);

    // int val = getgcd(p2.x);

    // v = mergey(p1.x, mergey(p2.x, p2.y));

    // return val;

    if(v == -1)
        v = topy++;

    int res = 0;

    for(int i = ly; i <= ry; ++i)
        res = gcd2(res, stupid[v][i]);

    return res;
}

int getx(int tl, int tr, int v, int lx, int rx, int ly, int ry)
{
    if(v == -1)
        return 0;

    if(tl > rx || tr < lx)
        return 0;

    if(tl >= lx && tr <= rx)
        return gety(tx[v].rooty, ly, ry);

    int mid = (tl + tr) / 2;

    return gcd2(getx(tl, mid, tx[v].l, lx, rx, ly, ry), getx(mid + 1, tr, tx[v].r, lx, rx, ly, ry));
}

int createy(int y, int val)
{
    int v = topy++;

    ty[v].y = y;
    ty[v].val = ty[v].gcd = val;

    return v;
}

void changey(int &v, int y, int val)
{
    // pii p1 = splity(v, y - 1);
    // pii p2 = splity(p1.y, y);

    // v = mergey(p1.x, mergey(createy(y, val), p2.y));

    if(v == -1)
        v = topy++;

    stupid[v][y] = val;
}

int changex(int tl, int tr, int v, int x, int y, int val)
{
    if(tl > x || tr < x)
        return v;

    if(v == -1)
        v = createx();

    changey(tx[v].rooty, y, val);

    if(tl == tr)
        return v;

    int mid = (tl + tr) / 2;

    tx[v].l = changex(tl, mid, tx[v].l, x, y, val);
    tx[v].r = changex(mid + 1, tr, tx[v].r, x, y, val);

    return v; 
}

void init(int32_t n, int32_t m) 
{
    ::n = n;
    ::m = m;

    for(int i = 0; i < 5010; ++i)
        for(int j = 0; j < 5010; ++j)
            stupid[i][j] = 0;
}

void update(int32_t x, int32_t y, ll val) 
{
    rootx = changex(0, (ll)n - 1, rootx, x, y, val);
}

long long calculate(int32_t x1, int32_t y1, int32_t x2, int32_t y2) 
{
    return getx(0, (ll)n - 1, rootx, x1, x2, y1, y2);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 205 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 172 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 256000 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 151 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -