oj.uz

Submission #406665

# Submission time Handle Problem Language Result Execution time Memory
406665 2021-05-18T02:06:17 Z Marceantasy Game (IOI13_game) C++17
100 / 100
 3600 ms 82124 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

static int R, C; 

struct X_NODE{
    X_NODE(int s, int e): s(s), e(e), left(NULL), right(NULL), value(0LL){}
    int s, e; 
    X_NODE *left, *right; 
    ll value; 
}; 

struct Y_NODE{
    Y_NODE(): left(NULL), right(NULL), xtree(1, C){}
    Y_NODE *left, *right; 
    X_NODE xtree; 
} *root;

ll gcd2(ll x, ll y){
    if(y == 0) return x; 
    return gcd2(y, x%y); 
}

void init(int r, int c){
    R = r, C = c; 
    root = new Y_NODE(); 
}


void update2(X_NODE *node, int q, ll val){
    int s = node->s, e = node->e, m = (s+e)/2; 
    if(s == e){
        node->value = val; 
        return; 
    }
    X_NODE **child = &(q <= m ? node->left : node->right);
    if(*child == NULL){
        *child = new X_NODE(q, q);
        (*child)->value = val; 
    }else if((*child)->s <= q && q<=(*child)->e){
        update2(*child, q, val); 
    }else{
        do{
            if(q <= m) e = m; 
            else s = m+1; 
            m = (s+e)/2; 
        }while((q<=m) == ((*child)->e <= m)); 
        X_NODE *nnode = new X_NODE(s, e); 
        if((*child)->e <= m) nnode->left = *child;
        else nnode->right = *child; 
        *child = nnode; 
        update2(*child, q, val); 
    }
    node->value = gcd2(
        node->left? node->left->value:0, 
        node->right? node->right->value: 0
    );
}

ll query2(X_NODE *node, int s, int e){
    if(node == NULL || node->s > e || node->e < s) return 0; 
    if(s <= node->s && node -> e <= e){
        return node->value; 
    }
    return gcd2(query2(node->left, s, e), query2(node->right, s, e)); 
}

void update1(Y_NODE *node, int s, int e, int p, int q, ll val){
    int m = (s+e)/2; 
    if(s == e){
        update2(&node->xtree, q, val); 
        return; 
    }
    if(p<=m){
        if(node->left == NULL) node->left = new Y_NODE(); 
        update1(node->left, s, m, p, q, val); 
    }else{
        if(node->right == NULL) node->right = new Y_NODE(); 
        update1(node->right, m+1, e, p, q, val); 
    }
    ll v = gcd2(
        node->left?query2(&node->left->xtree, q, q) : 0, 
        node->right?query2(&node->right->xtree, q, q) : 0
    );
    update2(&node->xtree, q, v); 
}

void update(int p, int q, ll val){
    ++p, ++q; 
    update1(root, 1, R, p, q, val); 
}

ll qry1(Y_NODE *node, int s, int e, int p, int q, int u, int v){
    if(node == NULL || s > u || e < p) return 0; 
    if(p <= s && e <= u) return query2(&node->xtree, q, v); 
    int m = (s+e) / 2; 
    return gcd2(
        qry1(node->left, s, m, p, q, u, v), 
        qry1(node->right, m+1, e, p, q, u, v) 
    );
}

ll calculate(int p, int q, int u, int v){
    ++p, ++q, ++u, ++v; 
    return qry1(root, 1, R, p, q, u, v);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 578 ms 12664 KB Output is correct
5 Correct 456 ms 12536 KB Output is correct
6 Correct 487 ms 10052 KB Output is correct
7 Correct 646 ms 9684 KB Output is correct
8 Correct 363 ms 8012 KB Output is correct
9 Correct 602 ms 9980 KB Output is correct
10 Correct 496 ms 9448 KB Output is correct
11 Correct 1 ms 288 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 292 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1078 ms 15592 KB Output is correct
13 Correct 1766 ms 8796 KB Output is correct
14 Correct 289 ms 5504 KB Output is correct
15 Correct 1991 ms 10500 KB Output is correct
16 Correct 238 ms 14008 KB Output is correct
17 Correct 761 ms 11024 KB Output is correct
18 Correct 1557 ms 15528 KB Output is correct
19 Correct 1087 ms 15732 KB Output is correct
20 Correct 1027 ms 15092 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 284 KB Output is correct
12 Correct 557 ms 12672 KB Output is correct
13 Correct 416 ms 12636 KB Output is correct
14 Correct 459 ms 9952 KB Output is correct
15 Correct 548 ms 9680 KB Output is correct
16 Correct 346 ms 8260 KB Output is correct
17 Correct 495 ms 9864 KB Output is correct
18 Correct 487 ms 9512 KB Output is correct
19 Correct 934 ms 15528 KB Output is correct
20 Correct 1642 ms 8912 KB Output is correct
21 Correct 275 ms 5700 KB Output is correct
22 Correct 1841 ms 10696 KB Output is correct
23 Correct 212 ms 14020 KB Output is correct
24 Correct 705 ms 11212 KB Output is correct
25 Correct 1285 ms 15536 KB Output is correct
26 Correct 1164 ms 15772 KB Output is correct
27 Correct 1000 ms 15088 KB Output is correct
28 Correct 557 ms 43208 KB Output is correct
29 Correct 1544 ms 45360 KB Output is correct
30 Correct 2762 ms 35156 KB Output is correct
31 Correct 2459 ms 28492 KB Output is correct
32 Correct 409 ms 10224 KB Output is correct
33 Correct 538 ms 10644 KB Output is correct
34 Correct 281 ms 39104 KB Output is correct
35 Correct 934 ms 26952 KB Output is correct
36 Correct 2012 ms 43192 KB Output is correct
37 Correct 1522 ms 43536 KB Output is correct
38 Correct 1521 ms 42864 KB Output is correct
39 Correct 1214 ms 35824 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 264 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 579 ms 12696 KB Output is correct
13 Correct 401 ms 12480 KB Output is correct
14 Correct 458 ms 10052 KB Output is correct
15 Correct 576 ms 9840 KB Output is correct
16 Correct 343 ms 8216 KB Output is correct
17 Correct 495 ms 9924 KB Output is correct
18 Correct 516 ms 9596 KB Output is correct
19 Correct 943 ms 15592 KB Output is correct
20 Correct 1656 ms 8836 KB Output is correct
21 Correct 268 ms 5572 KB Output is correct
22 Correct 1870 ms 10516 KB Output is correct
23 Correct 205 ms 14080 KB Output is correct
24 Correct 681 ms 11008 KB Output is correct
25 Correct 1358 ms 15660 KB Output is correct
26 Correct 1042 ms 15636 KB Output is correct
27 Correct 993 ms 15128 KB Output is correct
28 Correct 471 ms 43244 KB Output is correct
29 Correct 1362 ms 45468 KB Output is correct
30 Correct 2830 ms 35288 KB Output is correct
31 Correct 2381 ms 28584 KB Output is correct
32 Correct 413 ms 10124 KB Output is correct
33 Correct 526 ms 10744 KB Output is correct
34 Correct 274 ms 39108 KB Output is correct
35 Correct 963 ms 26972 KB Output is correct
36 Correct 1940 ms 43332 KB Output is correct
37 Correct 1459 ms 43436 KB Output is correct
38 Correct 1572 ms 42808 KB Output is correct
39 Correct 651 ms 81056 KB Output is correct
40 Correct 2232 ms 82124 KB Output is correct
41 Correct 3600 ms 67332 KB Output is correct
42 Correct 3274 ms 52572 KB Output is correct
43 Correct 496 ms 76740 KB Output is correct
44 Correct 515 ms 10848 KB Output is correct
45 Correct 1287 ms 35772 KB Output is correct
46 Correct 2633 ms 80904 KB Output is correct
47 Correct 2597 ms 80884 KB Output is correct
48 Correct 2493 ms 80584 KB Output is correct
49 Correct 1 ms 204 KB Output is correct