oj.uz

Submission #330923

# Submission time Handle Problem Language Result Execution time Memory
330923 2020-11-26T21:56:11 Z smax Game (IOI13_game) C++17
100 / 100
 8023 ms 48824 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

// Source: https://github.com/kth-competitive-programming/kactl/blob/master/content/various/BumpAllocator.h

static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}

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 492 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 2 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 1103 ms 6332 KB Output is correct
5 Correct 500 ms 6636 KB Output is correct
6 Correct 1418 ms 3760 KB Output is correct
7 Correct 1643 ms 3436 KB Output is correct
8 Correct 1046 ms 3180 KB Output is correct
9 Correct 1563 ms 3436 KB Output is correct
10 Correct 1370 ms 2960 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 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 1 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 1659 ms 8300 KB Output is correct
13 Correct 3718 ms 3208 KB Output is correct
14 Correct 565 ms 1516 KB Output is correct
15 Correct 4022 ms 4196 KB Output is correct
16 Correct 512 ms 5356 KB Output is correct
17 Correct 2183 ms 4328 KB Output is correct
18 Correct 3804 ms 5916 KB Output is correct
19 Correct 3283 ms 6216 KB Output is correct
20 Correct 3051 ms 5484 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 380 KB Output is correct
12 Correct 1090 ms 6636 KB Output is correct
13 Correct 493 ms 6764 KB Output is correct
14 Correct 1415 ms 3888 KB Output is correct
15 Correct 1628 ms 3564 KB Output is correct
16 Correct 1061 ms 3276 KB Output is correct
17 Correct 1569 ms 3528 KB Output is correct
18 Correct 1374 ms 3052 KB Output is correct
19 Correct 1652 ms 8048 KB Output is correct
20 Correct 3709 ms 3452 KB Output is correct
21 Correct 564 ms 1644 KB Output is correct
22 Correct 4018 ms 4204 KB Output is correct
23 Correct 517 ms 5612 KB Output is correct
24 Correct 2182 ms 4284 KB Output is correct
25 Correct 3761 ms 5848 KB Output is correct
26 Correct 3283 ms 5692 KB Output is correct
27 Correct 3071 ms 4940 KB Output is correct
28 Correct 1384 ms 17344 KB Output is correct
29 Correct 2473 ms 20716 KB Output is correct
30 Correct 5103 ms 14380 KB Output is correct
31 Correct 4493 ms 11292 KB Output is correct
32 Correct 781 ms 1224 KB Output is correct
33 Correct 1149 ms 1260 KB Output is correct
34 Correct 753 ms 17516 KB Output is correct
35 Correct 2592 ms 10192 KB Output is correct
36 Correct 5117 ms 17820 KB Output is correct
37 Correct 4062 ms 17940 KB Output is correct
38 Correct 4157 ms 17444 KB Output is correct
39 Correct 3335 ms 14316 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 1 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 1103 ms 6124 KB Output is correct
13 Correct 500 ms 6508 KB Output is correct
14 Correct 1409 ms 3180 KB Output is correct
15 Correct 1640 ms 3052 KB Output is correct
16 Correct 1048 ms 2848 KB Output is correct
17 Correct 1572 ms 3212 KB Output is correct
18 Correct 1374 ms 2812 KB Output is correct
19 Correct 1664 ms 7532 KB Output is correct
20 Correct 3709 ms 3180 KB Output is correct
21 Correct 561 ms 940 KB Output is correct
22 Correct 4025 ms 3832 KB Output is correct
23 Correct 508 ms 4972 KB Output is correct
24 Correct 2183 ms 4016 KB Output is correct
25 Correct 3938 ms 5436 KB Output is correct
26 Correct 3263 ms 5656 KB Output is correct
27 Correct 3054 ms 5184 KB Output is correct
28 Correct 1392 ms 17404 KB Output is correct
29 Correct 2478 ms 20668 KB Output is correct
30 Correct 5099 ms 14316 KB Output is correct
31 Correct 4491 ms 11300 KB Output is correct
32 Correct 778 ms 1004 KB Output is correct
33 Correct 1146 ms 1516 KB Output is correct
34 Correct 747 ms 17516 KB Output is correct
35 Correct 2563 ms 10396 KB Output is correct
36 Correct 5204 ms 18004 KB Output is correct
37 Correct 4074 ms 18156 KB Output is correct
38 Correct 4208 ms 17664 KB Output is correct
39 Correct 1963 ms 46904 KB Output is correct
40 Correct 4662 ms 48824 KB Output is correct
41 Correct 8023 ms 36832 KB Output is correct
42 Correct 7145 ms 29840 KB Output is correct
43 Correct 1606 ms 43884 KB Output is correct
44 Correct 1207 ms 11008 KB Output is correct
45 Correct 3390 ms 24612 KB Output is correct
46 Correct 6993 ms 47864 KB Output is correct
47 Correct 6991 ms 47940 KB Output is correct
48 Correct 6893 ms 47540 KB Output is correct
49 Correct 1 ms 364 KB Output is correct