oj.uz

Submission #909717

# Submission time Handle Problem Language Result Execution time Memory
909717 2024-01-17T11:05:15 Z JakobZorz Game (IOI13_game) C++17
80 / 100
 2709 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){}
};

const int SIZE1=15000000;
const int SIZE2=1000000;

int num1;
Tree1 trees1[SIZE1];

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){
        if(v==0)
            return -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[SIZE2];

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){
        if(v==0)
            return -1;
        node=num2++;
        if(num2>=SIZE2){
            cout<<"ERROR\n";
            exit(0);
        }
    }
    
    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:80:13: warning: 'Tree2::ch2' will be initialized after [-Wreorder]
   80 |     int ch1,ch2;
      |             ^~~
game.cpp:79:9: warning:   'int Tree2::val' [-Wreorder]
   79 |     int val;
      |         ^~~
game.cpp:81:5: warning:   when initialized here [-Wreorder]
   81 |     Tree2():ch1(-1),ch2(-1),val(-1){}
      |     ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 247120 KB Output is correct
2 Correct 53 ms 246868 KB Output is correct
3 Correct 52 ms 246864 KB Output is correct
4 Correct 51 ms 246872 KB Output is correct
5 Correct 52 ms 246808 KB Output is correct
6 Correct 52 ms 246876 KB Output is correct
7 Correct 51 ms 246864 KB Output is correct
8 Correct 52 ms 246764 KB Output is correct
9 Correct 57 ms 246812 KB Output is correct
10 Correct 51 ms 246864 KB Output is correct
11 Correct 52 ms 246864 KB Output is correct
12 Correct 52 ms 247128 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 246864 KB Output is correct
2 Correct 51 ms 246868 KB Output is correct
3 Correct 51 ms 246864 KB Output is correct
4 Correct 710 ms 250972 KB Output is correct
5 Correct 567 ms 251332 KB Output is correct
6 Correct 683 ms 247888 KB Output is correct
7 Correct 681 ms 247916 KB Output is correct
8 Correct 475 ms 248596 KB Output is correct
9 Correct 676 ms 247808 KB Output is correct
10 Correct 647 ms 247276 KB Output is correct
11 Correct 52 ms 247212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 246868 KB Output is correct
2 Correct 54 ms 246868 KB Output is correct
3 Correct 53 ms 246964 KB Output is correct
4 Correct 52 ms 246976 KB Output is correct
5 Correct 51 ms 246784 KB Output is correct
6 Correct 52 ms 246868 KB Output is correct
7 Correct 52 ms 246864 KB Output is correct
8 Correct 51 ms 247012 KB Output is correct
9 Correct 52 ms 246864 KB Output is correct
10 Correct 53 ms 246772 KB Output is correct
11 Correct 52 ms 246868 KB Output is correct
12 Correct 1221 ms 251272 KB Output is correct
13 Correct 1676 ms 247892 KB Output is correct
14 Correct 556 ms 247520 KB Output is correct
15 Correct 1793 ms 247908 KB Output is correct
16 Correct 658 ms 247620 KB Output is correct
17 Correct 900 ms 248260 KB Output is correct
18 Correct 1279 ms 248404 KB Output is correct
19 Correct 1156 ms 248096 KB Output is correct
20 Correct 1092 ms 247596 KB Output is correct
21 Correct 50 ms 246864 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 246868 KB Output is correct
2 Correct 51 ms 246868 KB Output is correct
3 Correct 54 ms 246864 KB Output is correct
4 Correct 52 ms 246768 KB Output is correct
5 Correct 50 ms 246844 KB Output is correct
6 Correct 52 ms 246832 KB Output is correct
7 Correct 51 ms 246864 KB Output is correct
8 Correct 50 ms 246864 KB Output is correct
9 Correct 54 ms 246864 KB Output is correct
10 Correct 54 ms 246876 KB Output is correct
11 Correct 54 ms 246980 KB Output is correct
12 Correct 668 ms 251016 KB Output is correct
13 Correct 548 ms 251360 KB Output is correct
14 Correct 648 ms 247916 KB Output is correct
15 Correct 668 ms 247696 KB Output is correct
16 Correct 473 ms 248480 KB Output is correct
17 Correct 660 ms 247780 KB Output is correct
18 Correct 654 ms 247408 KB Output is correct
19 Correct 1196 ms 250968 KB Output is correct
20 Correct 1654 ms 247760 KB Output is correct
21 Correct 557 ms 247520 KB Output is correct
22 Correct 1799 ms 247548 KB Output is correct
23 Correct 610 ms 247716 KB Output is correct
24 Correct 895 ms 248160 KB Output is correct
25 Correct 1209 ms 247896 KB Output is correct
26 Correct 1166 ms 248216 KB Output is correct
27 Correct 1105 ms 247468 KB Output is correct
28 Correct 471 ms 247796 KB Output is correct
29 Correct 1064 ms 250708 KB Output is correct
30 Correct 2709 ms 247724 KB Output is correct
31 Correct 2656 ms 247976 KB Output is correct
32 Correct 468 ms 247352 KB Output is correct
33 Correct 590 ms 247616 KB Output is correct
34 Correct 586 ms 247568 KB Output is correct
35 Correct 726 ms 248276 KB Output is correct
36 Correct 1306 ms 247892 KB Output is correct
37 Correct 1146 ms 248108 KB Output is correct
38 Correct 1088 ms 247684 KB Output is correct
39 Correct 1040 ms 248272 KB Output is correct
40 Correct 53 ms 246864 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 246840 KB Output is correct
2 Correct 54 ms 246864 KB Output is correct
3 Correct 55 ms 246868 KB Output is correct
4 Correct 51 ms 246960 KB Output is correct
5 Correct 51 ms 246924 KB Output is correct
6 Correct 54 ms 246876 KB Output is correct
7 Correct 52 ms 247032 KB Output is correct
8 Correct 51 ms 246864 KB Output is correct
9 Correct 53 ms 246952 KB Output is correct
10 Correct 52 ms 246868 KB Output is correct
11 Correct 53 ms 246744 KB Output is correct
12 Correct 673 ms 251112 KB Output is correct
13 Correct 542 ms 251132 KB Output is correct
14 Correct 701 ms 248180 KB Output is correct
15 Correct 652 ms 247756 KB Output is correct
16 Correct 471 ms 248400 KB Output is correct
17 Correct 683 ms 247740 KB Output is correct
18 Correct 662 ms 247688 KB Output is correct
19 Correct 1257 ms 251032 KB Output is correct
20 Correct 1677 ms 247664 KB Output is correct
21 Correct 566 ms 247508 KB Output is correct
22 Correct 1823 ms 247608 KB Output is correct
23 Correct 597 ms 247820 KB Output is correct
24 Correct 910 ms 248384 KB Output is correct
25 Correct 1255 ms 247952 KB Output is correct
26 Correct 1185 ms 248448 KB Output is correct
27 Correct 1099 ms 247560 KB Output is correct
28 Correct 474 ms 247776 KB Output is correct
29 Correct 1012 ms 250544 KB Output is correct
30 Correct 2689 ms 247448 KB Output is correct
31 Correct 2614 ms 247692 KB Output is correct
32 Correct 470 ms 247392 KB Output is correct
33 Correct 593 ms 247440 KB Output is correct
34 Correct 567 ms 248224 KB Output is correct
35 Correct 735 ms 248412 KB Output is correct
36 Correct 1443 ms 248020 KB Output is correct
37 Correct 1099 ms 248176 KB Output is correct
38 Correct 1075 ms 247900 KB Output is correct
39 Runtime error 668 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -