oj.uz

Submission #330895

# Submission time Handle Problem Language Result Execution time Memory
330895 2020-11-26T20:34:48 Z smax Game (IOI13_game) C++17
80 / 100
 4870 ms 256000 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 {
    long long ans;
    Node *l, *r;

    Node() : ans(0), l(NULL), r(NULL) {}
};

long long query(Node *p, int l, int r, int i, int j) {
    if (i > r || j < l || !p)
        return 0;
    if (i <= l && r <= j)
        return p->ans;
    int m = (l + r) / 2;
    return gcd2(query(p->l, l, m, i, j), query(p->r, m+1, r, i, j));
}

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

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

    Seg() : node(new Node()), 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, 0, n-1, 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_y(Node *p, Node *pl, Node *pr, int l, int r, int y, long long val) {
    if (l != r) {
        int m = (l + r) / 2;
        if (y <= m) {
            if (!p->l) p->l = new Node();
            update_y(p->l, pl ? pl->l : NULL, pr ? pr->l : NULL, l, m, y, val);
        } else {
            if (!p->r) p->r = new Node();
            update_y(p->r, pl ? pl->r : NULL, pr ? pr->r : NULL, m+1, r, y, val);
        }
    }
    p->ans = gcd2((pl ? pl->ans : 0), (pr ? pr->ans : 0));
}

void update(Seg *p, int l, int r, int x, int y, long long val) {
    if (l == r) {
        update(p->node, 0, n-1, 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_y(p->node, p->l ? p->l->node : NULL, p->r ? p->r->node : NULL, 0, n-1, y, val);
}

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, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, 0, _r, 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 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 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 376 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 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 551 ms 15340 KB Output is correct
5 Correct 410 ms 15104 KB Output is correct
6 Correct 531 ms 12908 KB Output is correct
7 Correct 609 ms 12652 KB Output is correct
8 Correct 386 ms 9964 KB Output is correct
9 Correct 580 ms 12652 KB Output is correct
10 Correct 534 ms 12140 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 2 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 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 912 ms 17132 KB Output is correct
13 Correct 1571 ms 8812 KB Output is correct
14 Correct 314 ms 5760 KB Output is correct
15 Correct 1869 ms 11628 KB Output is correct
16 Correct 240 ms 18156 KB Output is correct
17 Correct 842 ms 13932 KB Output is correct
18 Correct 1558 ms 19820 KB Output is correct
19 Correct 1266 ms 20008 KB Output is correct
20 Correct 1183 ms 19308 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 1 ms 364 KB Output is correct
3 Correct 1 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 544 ms 15416 KB Output is correct
13 Correct 402 ms 15340 KB Output is correct
14 Correct 512 ms 12652 KB Output is correct
15 Correct 572 ms 12500 KB Output is correct
16 Correct 381 ms 9964 KB Output is correct
17 Correct 566 ms 12652 KB Output is correct
18 Correct 514 ms 12140 KB Output is correct
19 Correct 924 ms 17132 KB Output is correct
20 Correct 1562 ms 8940 KB Output is correct
21 Correct 324 ms 5612 KB Output is correct
22 Correct 1864 ms 11500 KB Output is correct
23 Correct 234 ms 18156 KB Output is correct
24 Correct 866 ms 14316 KB Output is correct
25 Correct 1475 ms 19564 KB Output is correct
26 Correct 1242 ms 19820 KB Output is correct
27 Correct 1161 ms 19180 KB Output is correct
28 Correct 754 ms 199532 KB Output is correct
29 Correct 1787 ms 220524 KB Output is correct
30 Correct 4832 ms 159968 KB Output is correct
31 Correct 4621 ms 124000 KB Output is correct
32 Correct 601 ms 10476 KB Output is correct
33 Correct 750 ms 12524 KB Output is correct
34 Correct 517 ms 213996 KB Output is correct
35 Correct 1428 ms 115156 KB Output is correct
36 Correct 2614 ms 218328 KB Output is correct
37 Correct 2119 ms 218328 KB Output is correct
38 Correct 2128 ms 217744 KB Output is correct
39 Correct 1799 ms 169800 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.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 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 545 ms 15340 KB Output is correct
13 Correct 404 ms 15212 KB Output is correct
14 Correct 502 ms 12652 KB Output is correct
15 Correct 603 ms 12396 KB Output is correct
16 Correct 382 ms 9964 KB Output is correct
17 Correct 571 ms 12704 KB Output is correct
18 Correct 538 ms 12268 KB Output is correct
19 Correct 908 ms 17132 KB Output is correct
20 Correct 1538 ms 8812 KB Output is correct
21 Correct 317 ms 5612 KB Output is correct
22 Correct 1856 ms 11244 KB Output is correct
23 Correct 235 ms 18156 KB Output is correct
24 Correct 856 ms 14136 KB Output is correct
25 Correct 1481 ms 19860 KB Output is correct
26 Correct 1261 ms 19948 KB Output is correct
27 Correct 1161 ms 19436 KB Output is correct
28 Correct 773 ms 199532 KB Output is correct
29 Correct 1888 ms 220396 KB Output is correct
30 Correct 4870 ms 159968 KB Output is correct
31 Correct 4690 ms 124128 KB Output is correct
32 Correct 600 ms 10348 KB Output is correct
33 Correct 752 ms 12396 KB Output is correct
34 Correct 507 ms 213996 KB Output is correct
35 Correct 1410 ms 115180 KB Output is correct
36 Correct 2608 ms 218348 KB Output is correct
37 Correct 2147 ms 218348 KB Output is correct
38 Correct 2114 ms 217984 KB Output is correct
39 Runtime error 624 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -