oj.uz

Submission #261713

# Submission time Handle Problem Language Result Execution time Memory
261713 2020-08-12T02:46:06 Z smax Game (IOI13_game) C++17
37 / 100
 2185 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;
    int l, r;
    Node *left, *right;

    Node() {}

    Node(int _l, int _r) : ans(0), l(_l), r(_r), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Node(l, m);
            right = new Node(m+1, r);
        }
    }

    long long query(int i, int j) {
        if (i > r || j < l)
            return 0;
        if (i <= l && r <= j)
            return ans;

        extend();
        return gcd2(left->query(i, j), right->query(i, j));
    }

    void update(int idx, long long val) {
        if (l == r) {
            ans = val;
            return;
        }

        extend();
        int m = (l + r) / 2;
        if (idx <= m)
            left->update(idx, val);
        else
            right->update(idx, val);
        ans = gcd2(left->ans, right->ans);
    }
};

struct Seg {
    int n, l, r;
    Node yNode;
    Seg *left, *right;

    Seg() {}

    Seg(int _n, int _l, int _r) : n(_n), l(_l), r(_r), yNode(0, n-1), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Seg(n, l, m);
            right = new Seg(n, m+1, r);
        }
    }

    long long query(int ix, int iy, int jx, int jy) {
        if (ix > r || jx < l)
            return 0;
        if (ix <= l && r <= jx)
            return yNode.query(iy, jy);

        extend();
        return gcd2(left->query(ix, iy, jx, jy), right->query(ix, iy, jx, jy));
    }

    void update(int x, int y, long long val) {
        if (l == r) {
            yNode.update(y, val);
            return;
        }

        extend();
        int m = (l + r) / 2;
        if (x <= m)
            left->update(x, y, val);
        else
            right->update(x, y, val);
        update_y(&yNode, &left->yNode, &right->yNode, y, val);
    }

    void update_y(Node *cur, Node *curL, Node *curR, int y, long long val) {
        if (cur->l == cur->r) {
            cur->ans = gcd2(curL->ans, curR->ans);
            return;
        }

        cur->extend();
        curL->extend();
        curR->extend();
        int m = (cur->l + cur->r) / 2;
        if (y <= m)
            update_y(cur->left, curL->left, curR->left, y, val);
        else
            update_y(cur->right, curL->right, curR->right, y, val);
        cur->ans = gcd2(cur->left->ans, cur->right->ans);
    }
};

Seg st;

void init(int R, int C) {
    st = Seg(C, 0, R - 1);
}

void update(int P, int Q, long long K) {
    st.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return st.query(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 2 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 256 KB Output is correct

Subtask #2
27.0 / 27.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 1124 ms 50680 KB Output is correct
5 Correct 623 ms 41848 KB Output is correct
6 Correct 1303 ms 115704 KB Output is correct
7 Correct 1293 ms 115368 KB Output is correct
8 Correct 1120 ms 111876 KB Output is correct
9 Correct 1267 ms 116728 KB Output is correct
10 Correct 1256 ms 114968 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 360 KB Output is correct
12 Correct 1255 ms 51188 KB Output is correct
13 Correct 1396 ms 21240 KB Output is correct
14 Correct 873 ms 7416 KB Output is correct
15 Correct 1608 ms 32528 KB Output is correct
16 Correct 325 ms 74408 KB Output is correct
17 Runtime error 2147 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 2 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1175 ms 50808 KB Output is correct
13 Correct 563 ms 41848 KB Output is correct
14 Correct 1265 ms 115620 KB Output is correct
15 Correct 1354 ms 115340 KB Output is correct
16 Correct 1123 ms 111888 KB Output is correct
17 Correct 1256 ms 116728 KB Output is correct
18 Correct 1330 ms 114980 KB Output is correct
19 Correct 1188 ms 51320 KB Output is correct
20 Correct 1383 ms 21188 KB Output is correct
21 Correct 878 ms 7416 KB Output is correct
22 Correct 1600 ms 32408 KB Output is correct
23 Correct 322 ms 74360 KB Output is correct
24 Runtime error 2185 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 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 2 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1188 ms 50704 KB Output is correct
13 Correct 566 ms 41720 KB Output is correct
14 Correct 1267 ms 115556 KB Output is correct
15 Correct 1304 ms 115480 KB Output is correct
16 Correct 1112 ms 111864 KB Output is correct
17 Correct 1285 ms 116716 KB Output is correct
18 Correct 1237 ms 114988 KB Output is correct
19 Correct 1170 ms 51064 KB Output is correct
20 Correct 1408 ms 21120 KB Output is correct
21 Correct 882 ms 7416 KB Output is correct
22 Correct 1613 ms 32128 KB Output is correct
23 Correct 328 ms 74360 KB Output is correct
24 Runtime error 2162 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -