Submission #261708

#	Time	Username	Problem	Language	Result	Execution time	Memory
261708		smax	Game (IOI13_game)	C++17	0 / 100	1 ms	384 KiB

game

#include <bits/stdc++.h>
#include "game.h"

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, int 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 (stderr)

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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20