oj.uz

Submission #909696

# Submission time Handle Problem Language Result Execution time Memory
909696 2024-01-17T10:51:11 Z JakobZorz Game (IOI13_game) C++17
80 / 100
 2898 ms 256000 KB 
#include"game.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;

const int TREE_SIZE=1<<30;

ll gcd2(ll X,ll Y){
    ll tmp;
    while (X!=Y&&Y!=0){
        tmp=X;
        X=Y;
        Y=tmp%Y;
    }
    return X;
}

// ===============================================================
// ===============================================================
// ===============================================================

struct Tree1{
    ll val;
    int ch1,ch2;
    Tree1():val(0),ch1(-1),ch2(-1){}
};

int num1;
Tree1 trees1[9000000];

ll tree1_get_val(int node){
    if(node==-1)
        return 0;
    return trees1[node].val;
}

int tree1_set(int node,int rl,int rr,int x,ll v){
    if(node==-1)
        node=num1++;
    
    if(rl==rr-1){
        trees1[node].val=v;
        return node;
    }
    
    int mid=(rl+rr)/2;
    if(x<mid){
        trees1[node].ch1=tree1_set(trees1[node].ch1,rl,mid,x,v);
    }else{
        trees1[node].ch2=tree1_set(trees1[node].ch2,mid,rr,x,v);
    }
    trees1[node].val=gcd2(tree1_get_val(trees1[node].ch1),tree1_get_val(trees1[node].ch2));
    return node;
}

ll tree1_get(int node,int rl,int rr,int x1,int x2){
    if(node==-1)
        return 0;
    if(x2<=rl||rr<=x1)
        return 0;
    if(x1<=rl&&rr<=x2)
        return trees1[node].val;
    int mid=(rl+rr)/2;
    return gcd2(tree1_get(trees1[node].ch1,rl,mid,x1,x2),tree1_get(trees1[node].ch2,mid,rr,x1,x2));
}

// ===============================================================
// ===============================================================
// ===============================================================

struct Tree2{
    int val;
    int ch1,ch2;
    Tree2():ch1(-1),ch2(-1),val(-1){}
};

int num2;
Tree2 trees2[1000000];

ll tree2_get_val(int node,int x1,int x2){
    if(node==-1)
        return 0;
    return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
}

int tree2_set(int node,int rl,int rr,int x,int y,ll v){
    if(node==-1)
        node=num2++;
    
    if(rl==rr-1){
        trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,v);
        return node;
    }
    
    int mid=(rl+rr)/2;
    if(y<mid){
        trees2[node].ch1=tree2_set(trees2[node].ch1,rl,mid,x,y,v);
    }else{
        trees2[node].ch2=tree2_set(trees2[node].ch2,mid,rr,x,y,v);
    }
    ll val=gcd2(tree2_get_val(trees2[node].ch1,x,x+1),tree2_get_val(trees2[node].ch2,x,x+1));
    trees2[node].val=tree1_set(trees2[node].val,0,TREE_SIZE,x,val);
    return node;
}

ll tree2_get(int node,int rl,int rr,int x1,int x2,int y1,int y2){
    if(node==-1)
        return 0;
    if(y2<=rl||rr<=y1)
        return 0;
    if(y1<=rl&&rr<=y2)
        return tree1_get(trees2[node].val,0,TREE_SIZE,x1,x2);
    int mid=(rl+rr)/2;
    return gcd2(tree2_get(trees2[node].ch1,rl,mid,x1,x2,y1,y2),tree2_get(trees2[node].ch2,mid,rr,x1,x2,y1,y2));
}

// ===============================================================
// ===============================================================
// ===============================================================

void init(int h,int w){
    num2=1;
}

void update(int y,int x,ll v){
    tree2_set(0,0,TREE_SIZE,x,y,v);
}

ll calculate(int y1,int x1,int y2,int x2){
    return tree2_get(0,0,TREE_SIZE,x1,x2+1,y1,y2+1);
}

Compilation message

game.cpp: In constructor 'Tree2::Tree2()':
game.cpp:74:13: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
   74 |     int ch1,ch2;
      |             ^~~
game.cpp:73:9: warning:   'int Tree2::val' [-Wreorder]
   73 |     int val;
      |         ^~~
game.cpp:75:5: warning:   when initialized here [-Wreorder]
   75 |     Tree2():ch1(-1),ch2(-1),val(-1){}
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 152924 KB Output is correct
2 Correct 35 ms 152916 KB Output is correct
3 Correct 34 ms 152924 KB Output is correct
4 Correct 33 ms 152912 KB Output is correct
5 Correct 33 ms 152896 KB Output is correct
6 Correct 35 ms 152912 KB Output is correct
7 Correct 32 ms 152920 KB Output is correct
8 Correct 33 ms 152976 KB Output is correct
9 Correct 34 ms 152912 KB Output is correct
10 Correct 33 ms 152920 KB Output is correct
11 Correct 33 ms 152912 KB Output is correct
12 Correct 32 ms 152912 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 152996 KB Output is correct
2 Correct 33 ms 152916 KB Output is correct
3 Correct 32 ms 153260 KB Output is correct
4 Correct 659 ms 157260 KB Output is correct
5 Correct 530 ms 157524 KB Output is correct
6 Correct 623 ms 154196 KB Output is correct
7 Correct 652 ms 153940 KB Output is correct
8 Correct 459 ms 154804 KB Output is correct
9 Correct 650 ms 154048 KB Output is correct
10 Correct 603 ms 153580 KB Output is correct
11 Correct 32 ms 152916 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 153000 KB Output is correct
2 Correct 34 ms 152920 KB Output is correct
3 Correct 33 ms 152912 KB Output is correct
4 Correct 33 ms 152928 KB Output is correct
5 Correct 34 ms 152912 KB Output is correct
6 Correct 34 ms 152916 KB Output is correct
7 Correct 32 ms 152924 KB Output is correct
8 Correct 33 ms 152988 KB Output is correct
9 Correct 35 ms 152916 KB Output is correct
10 Correct 33 ms 152924 KB Output is correct
11 Correct 35 ms 152904 KB Output is correct
12 Correct 1252 ms 157124 KB Output is correct
13 Correct 1644 ms 153988 KB Output is correct
14 Correct 549 ms 153528 KB Output is correct
15 Correct 1800 ms 153708 KB Output is correct
16 Correct 578 ms 153692 KB Output is correct
17 Correct 888 ms 154440 KB Output is correct
18 Correct 1247 ms 154164 KB Output is correct
19 Correct 1169 ms 154612 KB Output is correct
20 Correct 1076 ms 153552 KB Output is correct
21 Correct 32 ms 152912 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 152916 KB Output is correct
2 Correct 34 ms 152920 KB Output is correct
3 Correct 33 ms 153012 KB Output is correct
4 Correct 33 ms 152924 KB Output is correct
5 Correct 33 ms 152916 KB Output is correct
6 Correct 34 ms 152872 KB Output is correct
7 Correct 33 ms 152916 KB Output is correct
8 Correct 34 ms 152916 KB Output is correct
9 Correct 34 ms 152912 KB Output is correct
10 Correct 33 ms 152912 KB Output is correct
11 Correct 33 ms 152928 KB Output is correct
12 Correct 660 ms 157052 KB Output is correct
13 Correct 522 ms 157316 KB Output is correct
14 Correct 628 ms 154144 KB Output is correct
15 Correct 690 ms 154228 KB Output is correct
16 Correct 467 ms 154448 KB Output is correct
17 Correct 644 ms 153800 KB Output is correct
18 Correct 617 ms 153800 KB Output is correct
19 Correct 1217 ms 157320 KB Output is correct
20 Correct 1652 ms 153980 KB Output is correct
21 Correct 565 ms 153564 KB Output is correct
22 Correct 1899 ms 153600 KB Output is correct
23 Correct 613 ms 153620 KB Output is correct
24 Correct 1018 ms 154576 KB Output is correct
25 Correct 1741 ms 154108 KB Output is correct
26 Correct 1553 ms 154216 KB Output is correct
27 Correct 1413 ms 153624 KB Output is correct
28 Correct 570 ms 157272 KB Output is correct
29 Correct 1180 ms 166652 KB Output is correct
30 Correct 2898 ms 160496 KB Output is correct
31 Correct 2702 ms 157296 KB Output is correct
32 Correct 525 ms 162800 KB Output is correct
33 Correct 626 ms 153856 KB Output is correct
34 Correct 590 ms 153680 KB Output is correct
35 Correct 904 ms 154748 KB Output is correct
36 Correct 1639 ms 154292 KB Output is correct
37 Correct 1157 ms 154452 KB Output is correct
38 Correct 1143 ms 153620 KB Output is correct
39 Correct 950 ms 154488 KB Output is correct
40 Correct 33 ms 152924 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 152916 KB Output is correct
2 Correct 34 ms 152912 KB Output is correct
3 Correct 34 ms 152920 KB Output is correct
4 Correct 32 ms 152836 KB Output is correct
5 Correct 33 ms 152924 KB Output is correct
6 Correct 34 ms 152976 KB Output is correct
7 Correct 33 ms 152952 KB Output is correct
8 Correct 32 ms 152916 KB Output is correct
9 Correct 34 ms 152916 KB Output is correct
10 Correct 33 ms 152884 KB Output is correct
11 Correct 34 ms 152892 KB Output is correct
12 Correct 671 ms 157000 KB Output is correct
13 Correct 553 ms 157356 KB Output is correct
14 Correct 647 ms 153976 KB Output is correct
15 Correct 722 ms 153820 KB Output is correct
16 Correct 522 ms 154492 KB Output is correct
17 Correct 673 ms 154012 KB Output is correct
18 Correct 616 ms 153660 KB Output is correct
19 Correct 1201 ms 157416 KB Output is correct
20 Correct 1669 ms 154044 KB Output is correct
21 Correct 547 ms 153428 KB Output is correct
22 Correct 1792 ms 153680 KB Output is correct
23 Correct 610 ms 153720 KB Output is correct
24 Correct 867 ms 154312 KB Output is correct
25 Correct 1279 ms 154052 KB Output is correct
26 Correct 1181 ms 154220 KB Output is correct
27 Correct 1089 ms 153528 KB Output is correct
28 Correct 458 ms 153564 KB Output is correct
29 Correct 1066 ms 156580 KB Output is correct
30 Correct 2775 ms 153872 KB Output is correct
31 Correct 2711 ms 153768 KB Output is correct
32 Correct 487 ms 153424 KB Output is correct
33 Correct 597 ms 153428 KB Output is correct
34 Correct 553 ms 153576 KB Output is correct
35 Correct 725 ms 154192 KB Output is correct
36 Correct 1366 ms 154084 KB Output is correct
37 Correct 1196 ms 154220 KB Output is correct
38 Correct 1080 ms 153476 KB Output is correct
39 Runtime error 2524 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -