oj.uz

Submission #281849

# Submission time Handle Problem Language Result Execution time Memory
281849 2020-08-23T14:42:52 Z amoo_safar Game (IOI13_game) C++17
0 / 100
 2 ms 512 KB 
#include "game.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Inf = 1e9 + 3;
const int LG = 30;
const int MX = 10010;

int lc[MX * LG * LG], rc[MX * LG * LG], la = 1;
ll g[MX * LG * LG];

void Set(int id, int idx, ll val, int L, int R){
    if(L + 1 == R){
        g[id] = val;
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!lc[id]) lc[id] = ++la;
        Set(lc[id], idx, val, L, mid);
    } else {
        if(!rc[id]) rc[id] = ++la;
        Set(rc[id], idx, val, mid, R);
    }
    g[id] = __gcd(lc[id] ? g[lc[id]] : 0, rc[id] ? g[rc[id]] : 0);
}

ll Get(int id, int l, int r, int L, int R){
    if(r <= L || R <= l) return 0;
    if(l <= L && R <= r) return g[id];
    int mid = (L + R) >> 1;
    return __gcd(lc[id] ? Get(lc[id], l, r, L, mid) : 0, rc[id] ? Get(rc[id], l, r, mid, R) : 0);
}

void Update(int id, int hl, int hr, int idx, int L, int R){
    if(L + 1 == R){
        g[id] = __gcd(g[hl], g[hr]);
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!lc[id]) lc[id] = ++la;
        Update(lc[id], lc[hl], lc[hr], idx, L, mid);
    } else {
        if(!rc[id]) rc[id] = ++la;
        Update(rc[id], rc[hl], rc[hr], idx, mid, R);
    }
    g[id] = __gcd(g[lc[id]], g[rc[id]]);
}

//Seg node[MX * LOG];

struct Seg2D {
    int ds;
    Seg2D *Lc, *Rc;
    Seg2D (){
        ds = ++la;
        Lc = NULL;
        Rc = NULL;
    }
    void Set2D(int x, int y, ll val, int L, int R){
        if(L + 1 == R){
            Set(ds, y, val, 0, Inf);
            return ;
        }
        int mid = (L + R) >> 1;
        if(x < mid){
            if(!Lc) Lc = new Seg2D();
            Lc -> Set2D(x, y, val, L, mid);
        } else {
            if(!Rc) Rc = new Seg2D();
            Rc -> Set2D(x, y, val, mid, R);
        }
        Update(ds, Lc ? Lc -> ds : 0, Lc ? Lc -> ds : 0, y, 0, Inf);
    }
    ll Get2D(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 Get(ds, ly, ry, 0, Inf);
        int mid = (L + R) >> 1;
        return __gcd(Lc ? Lc -> Get2D(lx, rx, ly, ry, L, mid) : 0, Rc ? Rc -> Get2D(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.Set2D(P, Q, K, 0, Inf);
}

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

Compilation message

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -