oj.uz

Submission #98507

# Submission time Handle Problem Language Result Execution time Memory
98507 2019-02-23T19:46:26 Z luciocf Game (IOI13_game) C++14
100 / 100
 11894 ms 52120 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;
    uint_fast64_t v, g;
    Node *l, *r;

    Node() {
        l = r = NULL;
        v = 0, g = 0, 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) 
{
    uint_fast64_t tmp;
    while (X != Y && Y != 0) 
    {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

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

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

uint_fast64_t 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;

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

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

    uint_fast64_t 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);
}

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

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

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

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

uint_fast64_t query_x(Node2d *nx, int tlx, int trx, int lx, int rx, int ly, int ry)
{
    if (nx == NULL || lx > rx) return 0;
    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:117:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (vl != -1) v = gcd(vl, v);
         ~~~^~~~~
game.cpp:118:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (vr != -1) v = gcd(vr, v);
         ~~~^~~~~
game.cpp:122:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (x == -1)
         ~~^~~~~
game.cpp:113: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 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 1174 ms 10744 KB Output is correct
5 Correct 527 ms 10488 KB Output is correct
6 Correct 2214 ms 8100 KB Output is correct
7 Correct 2639 ms 7744 KB Output is correct
8 Correct 1659 ms 7284 KB Output is correct
9 Correct 2480 ms 7816 KB Output is correct
10 Correct 2318 ms 7568 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1583 ms 12124 KB Output is correct
13 Correct 5308 ms 7096 KB Output is correct
14 Correct 630 ms 5752 KB Output is correct
15 Correct 5750 ms 8260 KB Output is correct
16 Correct 539 ms 9824 KB Output is correct
17 Correct 4075 ms 9124 KB Output is correct
18 Correct 7444 ms 11276 KB Output is correct
19 Correct 5990 ms 11480 KB Output is correct
20 Correct 6546 ms 10908 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1332 ms 10712 KB Output is correct
13 Correct 570 ms 10588 KB Output is correct
14 Correct 2205 ms 8056 KB Output is correct
15 Correct 2593 ms 7940 KB Output is correct
16 Correct 1695 ms 7324 KB Output is correct
17 Correct 2572 ms 8064 KB Output is correct
18 Correct 2602 ms 7492 KB Output is correct
19 Correct 1776 ms 12152 KB Output is correct
20 Correct 5323 ms 7096 KB Output is correct
21 Correct 681 ms 5624 KB Output is correct
22 Correct 6114 ms 8264 KB Output is correct
23 Correct 580 ms 9856 KB Output is correct
24 Correct 4035 ms 8944 KB Output is correct
25 Correct 7670 ms 11456 KB Output is correct
26 Correct 6076 ms 11708 KB Output is correct
27 Correct 6130 ms 10912 KB Output is correct
28 Correct 2289 ms 31596 KB Output is correct
29 Correct 2600 ms 29944 KB Output is correct
30 Correct 7552 ms 24028 KB Output is correct
31 Correct 6301 ms 20340 KB Output is correct
32 Correct 1095 ms 7416 KB Output is correct
33 Correct 1780 ms 7672 KB Output is correct
34 Correct 750 ms 27920 KB Output is correct
35 Correct 4520 ms 17836 KB Output is correct
36 Correct 9133 ms 27296 KB Output is correct
37 Correct 6819 ms 27476 KB Output is correct
38 Correct 7770 ms 26928 KB Output is correct
39 Correct 6087 ms 22824 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1134 ms 10868 KB Output is correct
13 Correct 540 ms 10488 KB Output is correct
14 Correct 2236 ms 8196 KB Output is correct
15 Correct 2535 ms 7888 KB Output is correct
16 Correct 1614 ms 7168 KB Output is correct
17 Correct 2693 ms 7976 KB Output is correct
18 Correct 2556 ms 7376 KB Output is correct
19 Correct 1878 ms 12000 KB Output is correct
20 Correct 5292 ms 7176 KB Output is correct
21 Correct 780 ms 5712 KB Output is correct
22 Correct 5847 ms 8292 KB Output is correct
23 Correct 612 ms 9984 KB Output is correct
24 Correct 3969 ms 9072 KB Output is correct
25 Correct 7558 ms 11592 KB Output is correct
26 Correct 6160 ms 11420 KB Output is correct
27 Correct 6501 ms 10876 KB Output is correct
28 Correct 2327 ms 31628 KB Output is correct
29 Correct 2786 ms 30064 KB Output is correct
30 Correct 7721 ms 24040 KB Output is correct
31 Correct 6212 ms 20080 KB Output is correct
32 Correct 951 ms 7296 KB Output is correct
33 Correct 1660 ms 7968 KB Output is correct
34 Correct 823 ms 27896 KB Output is correct
35 Correct 4557 ms 17816 KB Output is correct
36 Correct 9302 ms 27728 KB Output is correct
37 Correct 7386 ms 27424 KB Output is correct
38 Correct 8514 ms 26804 KB Output is correct
39 Correct 3049 ms 50060 KB Output is correct
40 Correct 5092 ms 52120 KB Output is correct
41 Correct 10444 ms 41940 KB Output is correct
42 Correct 9767 ms 33648 KB Output is correct
43 Correct 1555 ms 51064 KB Output is correct
44 Correct 1063 ms 7292 KB Output is correct
45 Correct 6069 ms 22912 KB Output is correct
46 Correct 11517 ms 50740 KB Output is correct
47 Correct 11374 ms 50608 KB Output is correct
48 Correct 11894 ms 50092 KB Output is correct
49 Correct 2 ms 256 KB Output is correct