oj.uz

Submission #330918

# Submission time Handle Problem Language Result Execution time Memory
330918 2020-11-26T21:41:47 Z smax Game (IOI13_game) C++17
80 / 100
 4857 ms 256004 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-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 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 384 KB Output is correct
11 Correct 1 ms 376 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 659 ms 11880 KB Output is correct
5 Correct 429 ms 12396 KB Output is correct
6 Correct 498 ms 9228 KB Output is correct
7 Correct 631 ms 9020 KB Output is correct
8 Correct 380 ms 6948 KB Output is correct
9 Correct 597 ms 8940 KB Output is correct
10 Correct 540 ms 8536 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 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 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 918 ms 14388 KB Output is correct
13 Correct 1574 ms 6252 KB Output is correct
14 Correct 332 ms 2284 KB Output is correct
15 Correct 1850 ms 8324 KB Output is correct
16 Correct 203 ms 15340 KB Output is correct
17 Correct 929 ms 10348 KB Output is correct
18 Correct 1564 ms 15656 KB Output is correct
19 Correct 1333 ms 15852 KB Output is correct
20 Correct 1244 ms 15212 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 598 ms 11852 KB Output is correct
13 Correct 453 ms 12268 KB Output is correct
14 Correct 510 ms 9264 KB Output is correct
15 Correct 565 ms 8812 KB Output is correct
16 Correct 408 ms 6892 KB Output is correct
17 Correct 555 ms 9008 KB Output is correct
18 Correct 521 ms 8556 KB Output is correct
19 Correct 914 ms 14444 KB Output is correct
20 Correct 1526 ms 6380 KB Output is correct
21 Correct 313 ms 2284 KB Output is correct
22 Correct 1829 ms 8256 KB Output is correct
23 Correct 261 ms 15340 KB Output is correct
24 Correct 859 ms 10604 KB Output is correct
25 Correct 1528 ms 15748 KB Output is correct
26 Correct 1326 ms 16108 KB Output is correct
27 Correct 1228 ms 15468 KB Output is correct
28 Correct 779 ms 190444 KB Output is correct
29 Correct 1791 ms 211564 KB Output is correct
30 Correct 4857 ms 154720 KB Output is correct
31 Correct 4562 ms 118544 KB Output is correct
32 Correct 604 ms 2796 KB Output is correct
33 Correct 744 ms 4588 KB Output is correct
34 Correct 461 ms 208492 KB Output is correct
35 Correct 1398 ms 106940 KB Output is correct
36 Correct 2630 ms 209096 KB Output is correct
37 Correct 2151 ms 209388 KB Output is correct
38 Correct 2176 ms 208584 KB Output is correct
39 Correct 1822 ms 161004 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 586 ms 12140 KB Output is correct
13 Correct 411 ms 12268 KB Output is correct
14 Correct 497 ms 9068 KB Output is correct
15 Correct 569 ms 8812 KB Output is correct
16 Correct 373 ms 6764 KB Output is correct
17 Correct 557 ms 9324 KB Output is correct
18 Correct 512 ms 8684 KB Output is correct
19 Correct 911 ms 14444 KB Output is correct
20 Correct 1538 ms 6252 KB Output is correct
21 Correct 313 ms 2412 KB Output is correct
22 Correct 1838 ms 8300 KB Output is correct
23 Correct 203 ms 15596 KB Output is correct
24 Correct 869 ms 10476 KB Output is correct
25 Correct 1563 ms 15996 KB Output is correct
26 Correct 1291 ms 16104 KB Output is correct
27 Correct 1236 ms 15268 KB Output is correct
28 Correct 778 ms 190316 KB Output is correct
29 Correct 1861 ms 211436 KB Output is correct
30 Correct 4807 ms 154300 KB Output is correct
31 Correct 4567 ms 118124 KB Output is correct
32 Correct 598 ms 2284 KB Output is correct
33 Correct 745 ms 4332 KB Output is correct
34 Correct 459 ms 208108 KB Output is correct
35 Correct 1412 ms 106348 KB Output is correct
36 Correct 2634 ms 208620 KB Output is correct
37 Correct 2162 ms 209004 KB Output is correct
38 Correct 2169 ms 208236 KB Output is correct
39 Runtime error 623 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -