oj.uz

Submission #330925

# Submission time Handle Problem Language Result Execution time Memory
330925 2020-11-26T22:01:59 Z smax Game (IOI13_game) C++17
100 / 100
 7661 ms 47076 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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

struct Node {
    int key, priority;
    long long val, ans;
    Node *l, *r;

    Node(int _key, long long _val) : key(_key), priority(rand() + (rand() << 15)), val(_val), ans(_val), l(NULL), r(NULL) {}
};
typedef Node* pNode;

long long ans(pNode t) {
    return t ? t->ans : 0;
}

void pull(pNode t) {
    if (t) t->ans = gcd2(gcd2(ans(t->l), ans(t->r)), t->val);
}

void split(pNode t, int key, pNode &l, pNode &r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        split(t->l, key, l, t->l), r = t;
    else
        split(t->r, key, t->r, r), l = t;
    pull(t);
}

void merge(pNode &t, pNode l, pNode r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->priority > r->priority)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;
    pull(t);
}

long long query(pNode t, int l, int r) {
    pNode pl, pm, pr;
    split(t, l-1, pl, pm);
    split(pm, r, t, pr);
    long long ret = ans(t);
    merge(pm, pl, t);
    merge(t, pm, pr);
    return ret;
}

void update(pNode &t, int p, long long val) {
    pNode pl, pm, pr;
    split(t, p-1, pl, pm);
    split(pm, p, t, pr);
    if (t) t->val = t->ans = val;
    else t = new Node(p, val);
    merge(pm, pl, t);
    merge(t, pm, pr);
}

struct Seg {
    pNode node;
    Seg *l, *r;

    Seg() : node(NULL), l(NULL), r(NULL) {}
};

int n, _r;

long long query(Seg *p, int l, int r, int ix, int iy, int jx, int jy) {
    if (ix > r || jx < l || !p)
        return 0;
    if (ix <= l && r <= jx)
        return query(p->node, iy, jy);
    int m = (l + r) / 2;
    return gcd2(query(p->l, l, m, ix, iy, jx, jy), query(p->r, m+1, r, ix, iy, jx, jy));
}

void update(Seg *p, int l, int r, int x, int y, long long val) {
    if (l == r) {
        update(p->node, y, val);
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        if (!p->l) p->l = new Seg();
        update(p->l, l, m, x, y, val);
    } else {
        if (!p->r) p->r = new Seg();
        update(p->r, m+1, r, x, y, val);
    }
    update(p->node, y, gcd2(p->l ? query(p->l->node, y, y) : 0, p->r ? query(p->r->node, y, y) : 0));
}

Seg st;

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

void update(int P, int Q, long long K) {
    update(&st, 0, _r-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, 0, _r-1, P, Q, U, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1125 ms 7188 KB Output is correct
5 Correct 518 ms 7404 KB Output is correct
6 Correct 1433 ms 4072 KB Output is correct
7 Correct 1753 ms 3880 KB Output is correct
8 Correct 1074 ms 3936 KB Output is correct
9 Correct 1612 ms 4284 KB Output is correct
10 Correct 1431 ms 3692 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 372 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1678 ms 8904 KB Output is correct
13 Correct 3741 ms 3820 KB Output is correct
14 Correct 558 ms 1752 KB Output is correct
15 Correct 4042 ms 4792 KB Output is correct
16 Correct 540 ms 6840 KB Output is correct
17 Correct 2247 ms 4812 KB Output is correct
18 Correct 4114 ms 7140 KB Output is correct
19 Correct 3454 ms 7404 KB Output is correct
20 Correct 3160 ms 6828 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1104 ms 7532 KB Output is correct
13 Correct 506 ms 7660 KB Output is correct
14 Correct 1454 ms 4460 KB Output is correct
15 Correct 1670 ms 4228 KB Output is correct
16 Correct 1052 ms 3936 KB Output is correct
17 Correct 1622 ms 4376 KB Output is correct
18 Correct 1429 ms 4168 KB Output is correct
19 Correct 1662 ms 9528 KB Output is correct
20 Correct 3706 ms 4716 KB Output is correct
21 Correct 560 ms 1900 KB Output is correct
22 Correct 4024 ms 5044 KB Output is correct
23 Correct 518 ms 7020 KB Output is correct
24 Correct 2231 ms 5356 KB Output is correct
25 Correct 3948 ms 7580 KB Output is correct
26 Correct 3333 ms 7508 KB Output is correct
27 Correct 3119 ms 6888 KB Output is correct
28 Correct 1398 ms 22252 KB Output is correct
29 Correct 2482 ms 25196 KB Output is correct
30 Correct 5099 ms 17968 KB Output is correct
31 Correct 4512 ms 14124 KB Output is correct
32 Correct 778 ms 2028 KB Output is correct
33 Correct 1161 ms 2048 KB Output is correct
34 Correct 756 ms 21820 KB Output is correct
35 Correct 2586 ms 12432 KB Output is correct
36 Correct 5201 ms 22244 KB Output is correct
37 Correct 4114 ms 22252 KB Output is correct
38 Correct 4200 ms 21612 KB Output is correct
39 Correct 3479 ms 17640 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1102 ms 6764 KB Output is correct
13 Correct 507 ms 7020 KB Output is correct
14 Correct 1429 ms 3820 KB Output is correct
15 Correct 1663 ms 3796 KB Output is correct
16 Correct 1053 ms 3692 KB Output is correct
17 Correct 1571 ms 3948 KB Output is correct
18 Correct 1390 ms 3308 KB Output is correct
19 Correct 1664 ms 9024 KB Output is correct
20 Correct 3720 ms 3524 KB Output is correct
21 Correct 562 ms 1644 KB Output is correct
22 Correct 4006 ms 4588 KB Output is correct
23 Correct 519 ms 6508 KB Output is correct
24 Correct 2226 ms 5228 KB Output is correct
25 Correct 3981 ms 6892 KB Output is correct
26 Correct 3355 ms 6892 KB Output is correct
27 Correct 3148 ms 6252 KB Output is correct
28 Correct 1406 ms 21868 KB Output is correct
29 Correct 2448 ms 25264 KB Output is correct
30 Correct 5139 ms 17952 KB Output is correct
31 Correct 4472 ms 14188 KB Output is correct
32 Correct 779 ms 1388 KB Output is correct
33 Correct 1148 ms 1900 KB Output is correct
34 Correct 753 ms 21868 KB Output is correct
35 Correct 2602 ms 12620 KB Output is correct
36 Correct 5242 ms 22608 KB Output is correct
37 Correct 4148 ms 22512 KB Output is correct
38 Correct 4162 ms 21996 KB Output is correct
39 Correct 1977 ms 44652 KB Output is correct
40 Correct 4314 ms 47076 KB Output is correct
41 Correct 7661 ms 35736 KB Output is correct
42 Correct 7034 ms 26908 KB Output is correct
43 Correct 1606 ms 44652 KB Output is correct
44 Correct 1196 ms 1004 KB Output is correct
45 Correct 3390 ms 17332 KB Output is correct
46 Correct 7036 ms 45252 KB Output is correct
47 Correct 7029 ms 45196 KB Output is correct
48 Correct 6748 ms 44636 KB Output is correct
49 Correct 1 ms 364 KB Output is correct