oj.uz

Submission #76084

# Submission time Handle Problem Language Result Execution time Memory
76084 2018-09-12T03:38:37 Z luciocf Game (IOI13_game) C++14
63 / 100
 9268 ms 257024 KB 
// IOI 2013 - Game
// Lúcio Cardoso

#include <bits/stdc++.h>
#include <game.h>

using namespace std;

typedef long long ll;

int n, m;

struct Node {
    int w, ind;
    ll v, g;
    Node *l, *r;

    Node() {
        l = r = NULL;
        v = 0LL, g = 0LL, ind = -1;
        w = rand();
    }
};

typedef Node*& node_t;

struct Node2d {
    Node *f;
    Node2d *l, *r;

    Node2d() {
        f = NULL;
        l = r = NULL;
    }
};

Node2d *root = new Node2d;

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

ll get(Node *t)
{
    if (!t) return 0LL;
    return t->g;
}

void operation(Node *t)
{
    if (!t) return;
    t->g = gcd( gcd(t->v, get(t->l)), get(t->r));
}

ll find(node_t t, int v, ll k)
{
    if (!t) return -1LL;

    if (t->ind == v)
    {
        if (k != -1) t->v = k, operation(t);
        return t->v;
    }
    else if (t->ind > v)
    {
        ll x = find(t->l, v, k);
        if (x != -1 && k != -1) operation(t);
        return x;
    }
    else
    {
        ll x = find(t->r, v, k);
        if (x != -1 && k != -1) operation(t);
        return x;
    }
}

void split(Node *t, node_t l, node_t r, int pos)
{
    if (!t) return void(l=r=NULL);

    if (pos < t->ind)
        split(t->l, l, t->l, pos), r = t;
    else
        split(t->r, t->r, r, pos), l = t;
    operation(t);
}

void merge(node_t t, Node *l, Node *r)
{
    if (l == NULL)
        t = r;
    else if (r == NULL)
        t = l;
    else if (l->w >= r->w)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;
    operation(t);
}

void upd_y(node_t t, Node *left, Node *right, int pos, ll v)
{
    Node *tl = NULL, *tm = NULL, *tr = NULL;

    ll vl = find(left, pos, -1), vr = find(right, pos, -1);

    if (vl != -1) v = gcd(vl, v);
    if (vr != -1) v = gcd(vr, v);

    ll x = find(t, pos, v);

    if (x == -1)
    {
        Node *aux = new Node;
        aux->v = v, aux->ind = pos, aux->g = v;

        split(t, tl, tr, pos-1);
        merge(tl, tl, aux);
        merge(t, tl, tr);
    }
}

void upd_x(Node2d *nx, int lx, int rx, int x, int y, ll v)
{
    if (lx != rx)
    {
        int mx = (lx+rx)/2;
        if (x <= mx)
        {
            if (nx->l == NULL) nx->l = new Node2d;
            upd_x(nx->l, lx, mx, x, y, v);
        }
        else
        {
            if (nx->r == NULL) nx->r = new Node2d;
            upd_x(nx->r, mx+1, rx, x, y, v);
        }
    }
    upd_y(nx->f, (nx->l==NULL)?NULL:nx->l->f, (nx->r==NULL)?NULL:nx->r->f, y, v);
}

ll query_y(node_t t, int l, int r)
{
    if (!t) return 0LL;

    Node *tl = NULL, *tm = NULL, *tr = NULL;

    split(t, tl, tm, l-1);
    split(tm, t, tr, r);

    ll ans = 0LL;
    if (t) ans = t->g;
    merge(tm, tl, t);
    merge(t, tm, tr);
    return ans;
}

ll query_x(Node2d *nx, int tlx, int trx, int lx, int rx, int ly, int ry)
{
    if (nx == NULL || lx > rx) return 0LL;
    if (tlx == lx && trx == rx) return query_y(nx->f, ly, ry);

    int mx = (tlx+trx)/2;

    ll p1 = query_x(nx->l, tlx, mx, lx, min(rx, mx), ly, ry);
    ll p2 = query_x(nx->r, mx+1, trx, max(lx, mx+1), rx, ly, ry);

    return gcd(p1, p2);
}

void init(int R, int C)
{
    n = R, m = C;
    return;
}

void update(int P, int Q, long long K)
{
    upd_x(root, 0, n-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V)
{
    return query_x(root, 0, n-1, P, U, Q, V);
}

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;
      ^~~
game.cpp: In function 'void upd_y(node_t, Node*, Node*, int, ll)':
game.cpp:112:23: warning: unused variable 'tm' [-Wunused-variable]
     Node *tl = NULL, *tm = NULL, *tr = NULL;
                       ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 516 KB Output is correct
5 Correct 2 ms 524 KB Output is correct
6 Correct 3 ms 524 KB Output is correct
7 Correct 2 ms 524 KB Output is correct
8 Correct 2 ms 524 KB Output is correct
9 Correct 3 ms 544 KB Output is correct
10 Correct 3 ms 652 KB Output is correct
11 Correct 3 ms 652 KB Output is correct
12 Correct 2 ms 652 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 668 KB Output is correct
2 Correct 2 ms 668 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 1378 ms 11104 KB Output is correct
5 Correct 571 ms 15404 KB Output is correct
6 Correct 2769 ms 16952 KB Output is correct
7 Correct 3113 ms 21304 KB Output is correct
8 Correct 2149 ms 25192 KB Output is correct
9 Correct 3243 ms 30276 KB Output is correct
10 Correct 2912 ms 34584 KB Output is correct
11 Correct 3 ms 34584 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 34584 KB Output is correct
2 Correct 3 ms 34584 KB Output is correct
3 Correct 3 ms 34584 KB Output is correct
4 Correct 2 ms 34584 KB Output is correct
5 Correct 2 ms 34584 KB Output is correct
6 Correct 3 ms 34584 KB Output is correct
7 Correct 2 ms 34584 KB Output is correct
8 Correct 3 ms 34584 KB Output is correct
9 Correct 3 ms 34584 KB Output is correct
10 Correct 3 ms 34584 KB Output is correct
11 Correct 3 ms 34584 KB Output is correct
12 Correct 2095 ms 43952 KB Output is correct
13 Correct 6633 ms 43952 KB Output is correct
14 Correct 891 ms 45400 KB Output is correct
15 Correct 7180 ms 52752 KB Output is correct
16 Correct 525 ms 58792 KB Output is correct
17 Correct 4648 ms 62072 KB Output is correct
18 Correct 8076 ms 69404 KB Output is correct
19 Correct 6585 ms 74940 KB Output is correct
20 Correct 7528 ms 79740 KB Output is correct
21 Correct 3 ms 79740 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 79740 KB Output is correct
2 Correct 3 ms 79740 KB Output is correct
3 Correct 3 ms 79740 KB Output is correct
4 Correct 2 ms 79740 KB Output is correct
5 Correct 2 ms 79740 KB Output is correct
6 Correct 3 ms 79740 KB Output is correct
7 Correct 2 ms 79740 KB Output is correct
8 Correct 2 ms 79740 KB Output is correct
9 Correct 3 ms 79740 KB Output is correct
10 Correct 2 ms 79740 KB Output is correct
11 Correct 3 ms 79740 KB Output is correct
12 Correct 1404 ms 84820 KB Output is correct
13 Correct 571 ms 88844 KB Output is correct
14 Correct 2800 ms 90492 KB Output is correct
15 Correct 3130 ms 94876 KB Output is correct
16 Correct 2110 ms 98912 KB Output is correct
17 Correct 3040 ms 104024 KB Output is correct
18 Correct 3005 ms 108124 KB Output is correct
19 Correct 1901 ms 117420 KB Output is correct
20 Correct 6660 ms 117420 KB Output is correct
21 Correct 876 ms 118732 KB Output is correct
22 Correct 7305 ms 126296 KB Output is correct
23 Correct 503 ms 132196 KB Output is correct
24 Correct 4730 ms 135584 KB Output is correct
25 Correct 8253 ms 143076 KB Output is correct
26 Correct 6806 ms 148304 KB Output is correct
27 Correct 7438 ms 153076 KB Output is correct
28 Correct 2294 ms 179008 KB Output is correct
29 Correct 3009 ms 192244 KB Output is correct
30 Correct 8936 ms 192244 KB Output is correct
31 Correct 7887 ms 195484 KB Output is correct
32 Correct 1090 ms 195484 KB Output is correct
33 Correct 1936 ms 201752 KB Output is correct
34 Correct 842 ms 228408 KB Output is correct
35 Correct 5244 ms 228660 KB Output is correct
36 Correct 9268 ms 249256 KB Output is correct
37 Runtime error 7458 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
38 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
2 Halted 0 ms 0 KB -