oj.uz

Submission #281823

# Submission time Handle Problem Language Result Execution time Memory
281823 2020-08-23T14:11:14 Z amoo_safar Game (IOI13_game) C++17
36 / 100
 1546 ms 20000 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Runtime error 1 ms 512 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 852 ms 17068 KB Output is correct
13 Correct 1282 ms 7204 KB Output is correct
14 Correct 351 ms 1344 KB Output is correct
15 Correct 1370 ms 9592 KB Output is correct
16 Correct 318 ms 19448 KB Output is correct
17 Correct 889 ms 12408 KB Output is correct
18 Correct 1546 ms 19832 KB Output is correct
19 Correct 1318 ms 20000 KB Output is correct
20 Correct 1273 ms 19412 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 1 ms 512 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Runtime error 1 ms 512 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -