Submission #281823

#	Time	Username	Problem	Language	Result	Execution time	Memory
281823		amoo_safar	Game (IOI13_game)	C++17	36 / 100	1546 ms	20000 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Inf = 3e3 + 3;

struct Seg {
    ll g;
    Seg *lc, *rc;
    Seg (){
        g = 0;
        lc = NULL;
        rc = NULL;
    }
    void Set(int idx, ll val, int L, int R){
        if(L + 1 == R){
            g = val;
            return ;
        }
        int mid = (L + R) >> 1;
        if(idx < mid){
            if(!lc) lc = new Seg();
            lc -> Set(idx, val, L, mid);
        } else {
            if(!rc) rc = new Seg();
            rc -> Set(idx, val, mid, R);
        }
        g = __gcd(lc ? lc -> g : 0, rc ? rc -> g : 0);
    }
    ll Get(int l, int r, int L, int R){
        if(r <= L || R <= l) return 0;
        if(l <= L && R <= r) return g;
        int mid = (L + R) >> 1;
        return __gcd(lc ? lc -> Get(l, r, L, mid) : 0, rc ? rc -> Get(l, r, mid, R) : 0);
    }
    void Update(Seg *hl, Seg *hr, int idx, int L, int R){
        if(L + 1 == R){
            g = __gcd(hl ? hl -> g : 0, hr ? hr -> g : 0);
            return ;
        }
        int mid = (L + R) >> 1;
        if(idx < mid){
            if(!lc) lc = new Seg();
            lc -> Update(hl ? hl -> lc : NULL, hr ? hr -> lc : NULL, idx, L, mid);
        } else {
            if(!rc) rc = new Seg();
            rc -> Update(hl ? hl -> rc : NULL, hr ? hr -> rc : NULL, idx, mid, R);
        }
        g = __gcd(lc ? lc -> g : 0, rc ? rc -> g : 0);
    }
};

struct Seg2D {
    Seg *ds;
    Seg2D *lc, *rc;
    Seg2D (){
        ds = new Seg();
        lc = NULL;
        rc = NULL;
    }
    void Set(int x, int y, ll val, int L, int R){
        if(L + 1 == R){
            ds -> Set(y, val, 0, Inf);
            return ;
        }
        int mid = (L + R) >> 1;
        if(x < mid){
            if(!lc) lc = new Seg2D();
            lc -> Set(x, y, val, L, mid);
        } else {
            if(!rc) rc = new Seg2D();
            rc -> Set(x, y, val, mid, R);
        }
        ds -> Update(lc ? lc -> ds : NULL, rc ? rc -> ds : NULL, y, 0, Inf);
    }
    ll Get(int lx, int rx, int ly, int ry, int L, int R){
        if(rx <= L || R <= lx) return 0;
        if(lx <= L && R <= rx) return ds -> Get(ly, ry, 0, Inf);
        int mid = (L + R) >> 1;
        return __gcd(lc ? lc -> Get(lx, rx, ly, ry, L, mid) : 0, rc ? rc -> Get(lx, rx, ly, ry, mid, R) : 0);
    }
};
Seg2D Board;

void init(int R, int C) {
    assert(R <= Inf);
    assert(C <= Inf);
}

void update(int P, int Q, ll K) {
    Board.Set(P, Q, K, 0, Inf);
}

ll calculate(int P, int Q, int U, int V) {
    return Board.Get(P, U + 1, Q, V + 1, 0, Inf);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

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