oj.uz

Submission #281853

# Submission time Handle Problem Language Result Execution time Memory
281853 2020-08-23T14:46:40 Z amoo_safar Game (IOI13_game) C++17
80 / 100
 4279 ms 256000 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(g[lc[id]], g[rc[id]]);
}

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, Rc ? Rc -> 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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 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 2 ms 512 KB Output is correct
7 Correct 0 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 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 815 ms 27368 KB Output is correct
5 Correct 618 ms 27512 KB Output is correct
6 Correct 798 ms 24312 KB Output is correct
7 Correct 937 ms 24064 KB Output is correct
8 Correct 637 ms 15276 KB Output is correct
9 Correct 947 ms 24376 KB Output is correct
10 Correct 825 ms 23940 KB Output is correct
11 Correct 0 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 0 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 1044 ms 11732 KB Output is correct
13 Correct 1446 ms 5112 KB Output is correct
14 Correct 420 ms 1144 KB Output is correct
15 Correct 1716 ms 7568 KB Output is correct
16 Correct 410 ms 12280 KB Output is correct
17 Correct 1110 ms 9088 KB Output is correct
18 Correct 1928 ms 12572 KB Output is correct
19 Correct 1586 ms 12844 KB Output is correct
20 Correct 1523 ms 12408 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 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 846 ms 27564 KB Output is correct
13 Correct 583 ms 27512 KB Output is correct
14 Correct 800 ms 24444 KB Output is correct
15 Correct 942 ms 24056 KB Output is correct
16 Correct 543 ms 15352 KB Output is correct
17 Correct 907 ms 24360 KB Output is correct
18 Correct 802 ms 23784 KB Output is correct
19 Correct 1054 ms 11768 KB Output is correct
20 Correct 1456 ms 5368 KB Output is correct
21 Correct 422 ms 1056 KB Output is correct
22 Correct 1713 ms 7416 KB Output is correct
23 Correct 418 ms 12384 KB Output is correct
24 Correct 1106 ms 9044 KB Output is correct
25 Correct 2021 ms 12664 KB Output is correct
26 Correct 1700 ms 12952 KB Output is correct
27 Correct 1545 ms 12240 KB Output is correct
28 Correct 813 ms 129248 KB Output is correct
29 Correct 2274 ms 144316 KB Output is correct
30 Correct 4054 ms 103800 KB Output is correct
31 Correct 3650 ms 79480 KB Output is correct
32 Correct 473 ms 1148 KB Output is correct
33 Correct 659 ms 2380 KB Output is correct
34 Correct 1004 ms 141432 KB Output is correct
35 Correct 1582 ms 72232 KB Output is correct
36 Correct 3187 ms 141540 KB Output is correct
37 Correct 2612 ms 142232 KB Output is correct
38 Correct 2475 ms 141764 KB Output is correct
39 Correct 2142 ms 109588 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 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 2 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 843 ms 27896 KB Output is correct
13 Correct 611 ms 27932 KB Output is correct
14 Correct 834 ms 24980 KB Output is correct
15 Correct 871 ms 24568 KB Output is correct
16 Correct 564 ms 15868 KB Output is correct
17 Correct 907 ms 24668 KB Output is correct
18 Correct 882 ms 24312 KB Output is correct
19 Correct 1087 ms 12120 KB Output is correct
20 Correct 1506 ms 5680 KB Output is correct
21 Correct 420 ms 1656 KB Output is correct
22 Correct 1710 ms 8000 KB Output is correct
23 Correct 429 ms 12920 KB Output is correct
24 Correct 1275 ms 9632 KB Output is correct
25 Correct 2079 ms 13652 KB Output is correct
26 Correct 1672 ms 13824 KB Output is correct
27 Correct 1541 ms 13048 KB Output is correct
28 Correct 845 ms 129656 KB Output is correct
29 Correct 2349 ms 144784 KB Output is correct
30 Correct 4279 ms 104184 KB Output is correct
31 Correct 3773 ms 79876 KB Output is correct
32 Correct 479 ms 1400 KB Output is correct
33 Correct 677 ms 2680 KB Output is correct
34 Correct 1038 ms 141688 KB Output is correct
35 Correct 1619 ms 72568 KB Output is correct
36 Correct 3095 ms 141928 KB Output is correct
37 Correct 2566 ms 142200 KB Output is correct
38 Correct 2571 ms 141480 KB Output is correct
39 Runtime error 734 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -