Submission #855220

#	Time	Username	Problem	Language	Result	Execution time	Memory
855220		RamboJack	Game (IOI13_game)	C++17	0 / 100	1 ms	348 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;
}

class SegmentTree2D {
    int** tree, ** arr;
    int n, m;

    void buildY(int indy, int starty, int endy, int indx, int startx, int endx) {
        if (starty == endy) {
            if (startx == endx)
                tree[indx][indy] = arr[startx][starty];
            else
                tree[indx][indy] = tree[2 * indx][indy] + tree[2 * indx + 1][indy];
            return;
        }
        int mid = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
        buildY(lefty, starty, mid, indx, startx, endx);
        buildY(righty, mid + 1, endy, indx, startx, endx);
        tree[indx][indy] = tree[indx][lefty] + tree[indx][righty];
    }

    void buildX(int indx, int startx, int endx) {
        if (startx == endx) {
            buildY(1, 0, m - 1, indx, startx, endx);
            return;
        }
        int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1;
        buildX(leftx, startx, midx);
        buildX(rightx, midx + 1, endx);
        buildY(1, 0, m - 1, indx, startx, endx);
    }

    void updateY(int indy, int starty, int endy, int indx, int startx, int endx, int j, int val) {
        if (starty == endy) {
            if (startx == endx) {
                arr[startx][starty] = val; // update the original array as well
                tree[indx][indy] = val;
            } else
                tree[indx][indy] = tree[2 * indx][indy] + tree[2 * indx + 1][indy];
            return;
        }
        int midy = (starty + endy) / 2, lefty = 2 * indy, righty = lefty + 1;
        if (j <= midy)
            updateY(lefty, starty, midy, indx, startx, endx, j, val);
        else
            updateY(righty, midy + 1, endy, indx, startx, endx, j, val);
        tree[indx][indy] = tree[indx][lefty] + tree[indx][righty];
    }

    void updateX(int indx, int startX, int endX, int i, int j, int val) {
        if (startX == endX) {
            updateY(1, 0, m - 1, indx, startX, endX, j, val);
            return;
        }
        int midx = (startX + endX) / 2, leftx = 2 * indx, rightx = leftx + 1;
        if (i <= midx)
            updateX(leftx, startX, midx, i, j, val);
        else
            updateX(rightx, midx + 1, endX, i, j, val);
        updateY(1, 0, m - 1, indx, startX, endX, j, val);
    }

    int queryy(int indy, int starty, int endy, int indx, int startx, int endx, int j1, int j2) {
        if (j2 < starty or j1 > endy) // no overlap
            return 0;
        else if (j1 <= starty and endy <= j2) // complete overlap
            return tree[indx][indy];
        else { // partial overlap
            int midy = (starty + endy) / 2;
            int lefty = 2 * indy, righty = lefty + 1;
            int left = queryy(lefty, starty, midy, indx, startx, endx, j1, j2);
            int right = queryy(righty, midy + 1, endy, indx, startx, endx, j1, j2);
            return left + right;
        }
    }

    int queryx(int indx, int startx, int endx, int i1, int j1, int i2, int j2) {
        if (i2 < startx or i1 > endx) // no overlap
            return 0;
        else if (i1 <= startx and endx <= i2) // complete overlap
            return queryy(1, 0, m - 1, indx, startx, endx, j1, j2);
        int midx = (startx + endx) / 2, leftx = 2 * indx, rightx = leftx + 1; // partial overlap
        int left = queryx(leftx, startx, midx, i1, j1, i2, j2);
        int right = queryx(rightx, midx + 1, endx, i1, j1, i2, j2);
        return left + right;
    }
public:
    SegmentTree2D(int r, int c) {
        n = r;
        m = c;
        arr = new int* [n];
        for (int i = 0; i < n; i++)
            arr[i] = new int[m];
        tree = new int* [4 * n + 1];
        for (int i = 0; i < 4 * n + 1; i++)
            tree[i] = new int[4 * m + 1];
        buildX(1, 0, n - 1);
    }

    void update(int i, int j, int val) {
        updateX(1, 0, n - 1, i, j, val);
    }

    int query(int i1, int j1, int i2, int j2) {
        return queryx(1, 0, n - 1, i1, j1, i2, j2);
    }
};


SegmentTree2D* tree;

void init(int R, int C) {
    tree = new SegmentTree2D(R, C);
}

void update(int P, int Q, long long K) {
    tree->update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return tree->query(P, Q, U, V);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20