Submission #580003

#	Time	Username	Problem	Language	Result	Execution time	Memory
580003		MohamedFaresNebili	Game (IOI13_game)	C++14	0 / 100	1 ms	312 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        ll st[2001][2001];
        int R, C;

        void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, ll K) {
            if(ly == ry) {
                if(lx == rx)
                    st[vx][vy] = K;
                else st[vx][vy] = __gcd(st[vx * 2][vy], st[vx * 2 + 1][vy]);
                return;
            }
            int my = (ly + ry) / 2;
            if(y <= my)
                update_y(vx, lx, rx, vy * 2, ly, my, x, y, K);
            else update_y(vx, lx, rx, vy * 2 + 1, my + 1, ry, x, y, K);
            st[vx][vy] = __gcd(st[vx][vy * 2], st[vx][vy * 2 + 1]);
        }
        void update_x(int vx, int lx, int rx, int x, int y, ll K) {
            if(lx != rx) {
                int mx = (lx + rx) / 2;
                if(x <= mx)
                    update_x(vx * 2, lx, mx, x, y, K);
                else update_x(vx * 2 + 1, mx + 1, rx, x, y, K);
            }
            update_y(vx, lx, rx, 1, 0, C - 1, x, y, K);
        }
        int sum_y(int vx, int vy, int l, int r, int lo, int hi) {
            if(l > hi || r < lo) return -1;
            if(l >= lo && r <= hi) return st[vx][vy];
            int A = sum_y(vx, vy * 2, l, (l + r) / 2, lo, hi);
            int B = sum_y(vx, vy * 2 + 1, (l + r) / 2 + 1, r, lo, hi);
            if(A == -1) return B;
            if(B == -1) return A;
            return __gcd(A, B);
        }

        int sum_x(int vx, int l, int r, int lf, int rf, int lo, int hi) {
            if(l > rf || r < lf) return -1;
            if(l >= lf && r <= rf)
                return sum_y(vx, 1, 0, C - 1, lo, hi);
            int A = sum_x(vx * 2, l, (l + r) / 2, lf, rf, lo, hi);
            int B = sum_x(vx * 2 + 1, (l + r) / 2 + 1, r, lf, rf, lo, hi);
            if(A == -1) return B;
            if(B == -1) return A;
            return __gcd(A, B);
        }

        void init(int N, int M) {
            R = N; C = M;
        }
        void update(int P, int Q, ll K) {
            update_x(1, 0, R - 1, P, Q, K);
        }
        ll calculate(int P, int Q, int U, int V) {
            return sum_x(1, 0, R - 1, P, U, Q, V);
        }

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