oj.uz

Submission #261780

# Submission time Handle Problem Language Result Execution time Memory
261780 2020-08-12T04:58:17 Z smax Game (IOI13_game) C++17
63 / 100
 2033 ms 256004 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 {
    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);
}

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;
      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 608 ms 15896 KB Output is correct
5 Correct 471 ms 15960 KB Output is correct
6 Correct 582 ms 12792 KB Output is correct
7 Correct 663 ms 12740 KB Output is correct
8 Correct 448 ms 9504 KB Output is correct
9 Correct 612 ms 12588 KB Output is correct
10 Correct 583 ms 12308 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1010 ms 18424 KB Output is correct
13 Correct 1666 ms 8824 KB Output is correct
14 Correct 357 ms 3468 KB Output is correct
15 Correct 1951 ms 11620 KB Output is correct
16 Correct 279 ms 20856 KB Output is correct
17 Correct 919 ms 16360 KB Output is correct
18 Correct 1731 ms 23944 KB Output is correct
19 Correct 1352 ms 24360 KB Output is correct
20 Correct 1231 ms 23548 KB Output is correct
21 Correct 0 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 601 ms 15736 KB Output is correct
13 Correct 453 ms 16120 KB Output is correct
14 Correct 569 ms 12828 KB Output is correct
15 Correct 652 ms 12800 KB Output is correct
16 Correct 439 ms 9976 KB Output is correct
17 Correct 633 ms 13304 KB Output is correct
18 Correct 599 ms 13304 KB Output is correct
19 Correct 1014 ms 18552 KB Output is correct
20 Correct 1678 ms 8780 KB Output is correct
21 Correct 358 ms 3576 KB Output is correct
22 Correct 2033 ms 11388 KB Output is correct
23 Correct 286 ms 22008 KB Output is correct
24 Correct 877 ms 16556 KB Output is correct
25 Correct 1486 ms 24184 KB Output is correct
26 Correct 1333 ms 24144 KB Output is correct
27 Correct 1402 ms 23676 KB Output is correct
28 Correct 1101 ms 256000 KB Output is correct
29 Runtime error 1987 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 604 ms 15572 KB Output is correct
13 Correct 456 ms 15936 KB Output is correct
14 Correct 559 ms 14460 KB Output is correct
15 Correct 642 ms 14200 KB Output is correct
16 Correct 426 ms 11000 KB Output is correct
17 Correct 644 ms 14484 KB Output is correct
18 Correct 598 ms 13816 KB Output is correct
19 Correct 1059 ms 18552 KB Output is correct
20 Correct 1692 ms 8868 KB Output is correct
21 Correct 366 ms 3616 KB Output is correct
22 Correct 1964 ms 11468 KB Output is correct
23 Correct 280 ms 22060 KB Output is correct
24 Correct 883 ms 16760 KB Output is correct
25 Correct 1501 ms 24148 KB Output is correct
26 Correct 1289 ms 24120 KB Output is correct
27 Correct 1381 ms 23800 KB Output is correct
28 Correct 1125 ms 256000 KB Output is correct
29 Runtime error 1968 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -