oj.uz

Submission #281858

# Submission time Handle Problem Language Result Execution time Memory
281858 2020-08-23T14:52:19 Z amoo_safar Game (IOI13_game) C++17
80 / 100
 4252 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;
const int CNT = 13e6;
int lc[CNT], rc[CNT], la = 1;
ll g[CNT];


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 1 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 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 0 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 1 ms 384 KB Output is correct
4 Correct 871 ms 27256 KB Output is correct
5 Correct 622 ms 27512 KB Output is correct
6 Correct 816 ms 24824 KB Output is correct
7 Correct 1004 ms 24480 KB Output is correct
8 Correct 600 ms 15904 KB Output is correct
9 Correct 935 ms 24620 KB Output is correct
10 Correct 880 ms 24184 KB Output is correct
11 Correct 1 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 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 1076 ms 11648 KB Output is correct
13 Correct 1488 ms 4984 KB Output is correct
14 Correct 443 ms 1016 KB Output is correct
15 Correct 1746 ms 7416 KB Output is correct
16 Correct 427 ms 12280 KB Output is correct
17 Correct 1296 ms 9080 KB Output is correct
18 Correct 2005 ms 13048 KB Output is correct
19 Correct 1674 ms 13176 KB Output is correct
20 Correct 1593 ms 12588 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 256 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 830 ms 27256 KB Output is correct
13 Correct 615 ms 27640 KB Output is correct
14 Correct 839 ms 24952 KB Output is correct
15 Correct 966 ms 24696 KB Output is correct
16 Correct 577 ms 15828 KB Output is correct
17 Correct 875 ms 24828 KB Output is correct
18 Correct 846 ms 24184 KB Output is correct
19 Correct 1097 ms 12024 KB Output is correct
20 Correct 1494 ms 5408 KB Output is correct
21 Correct 439 ms 1400 KB Output is correct
22 Correct 1755 ms 7800 KB Output is correct
23 Correct 487 ms 12664 KB Output is correct
24 Correct 1220 ms 9464 KB Output is correct
25 Correct 1907 ms 13048 KB Output is correct
26 Correct 1632 ms 13176 KB Output is correct
27 Correct 1523 ms 12536 KB Output is correct
28 Correct 815 ms 129528 KB Output is correct
29 Correct 2292 ms 144636 KB Output is correct
30 Correct 4209 ms 104388 KB Output is correct
31 Correct 3832 ms 79864 KB Output is correct
32 Correct 471 ms 1528 KB Output is correct
33 Correct 672 ms 2808 KB Output is correct
34 Correct 994 ms 141816 KB Output is correct
35 Correct 1685 ms 72604 KB Output is correct
36 Correct 3092 ms 141980 KB Output is correct
37 Correct 2462 ms 141816 KB Output is correct
38 Correct 2578 ms 141136 KB Output is correct
39 Correct 2141 ms 109176 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 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 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 820 ms 27512 KB Output is correct
13 Correct 591 ms 27512 KB Output is correct
14 Correct 805 ms 24312 KB Output is correct
15 Correct 903 ms 24056 KB Output is correct
16 Correct 570 ms 15352 KB Output is correct
17 Correct 905 ms 24184 KB Output is correct
18 Correct 836 ms 23832 KB Output is correct
19 Correct 1069 ms 11640 KB Output is correct
20 Correct 1478 ms 4984 KB Output is correct
21 Correct 442 ms 1016 KB Output is correct
22 Correct 1753 ms 7664 KB Output is correct
23 Correct 457 ms 12444 KB Output is correct
24 Correct 1203 ms 9312 KB Output is correct
25 Correct 2140 ms 12680 KB Output is correct
26 Correct 1806 ms 12844 KB Output is correct
27 Correct 1719 ms 12152 KB Output is correct
28 Correct 831 ms 129144 KB Output is correct
29 Correct 2268 ms 144440 KB Output is correct
30 Correct 4252 ms 103876 KB Output is correct
31 Correct 3822 ms 79684 KB Output is correct
32 Correct 467 ms 1148 KB Output is correct
33 Correct 659 ms 2424 KB Output is correct
34 Correct 1000 ms 141572 KB Output is correct
35 Correct 1738 ms 72380 KB Output is correct
36 Correct 3107 ms 141848 KB Output is correct
37 Correct 2462 ms 141852 KB Output is correct
38 Correct 2481 ms 141400 KB Output is correct
39 Runtime error 1137 ms 256000 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -