oj.uz

Submission #854086

# Submission time Handle Problem Language Result Execution time Memory
854086 2023-09-26T06:09:08 Z abcvuitunggio Game (IOI13_game) C++17
100 / 100
 2198 ms 82176 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct Ty{
    int l,r;
    Ty* left;
    Ty* right;
    long long val;
    Ty(){};
    Ty(int l, int r){
        this->l=l;
        this->r=r;
        this->left=NULL;
        this->right=NULL;
        this->val=0LL;
    }
};
struct Tx{
    Tx* left;
    Tx* right;
    Ty t;
    Tx(){
        this->left=NULL;
        this->right=NULL;
        this->t=Ty(0,999999999);
    }
}*root;
void update2(Ty* node, int j, long long val){
    if (node->l>j||node->r<j)
        return;
    if (node->l==node->r){
        node->val=val;
        return;
    }
    int mid=(node->l+node->r)>>1;
    Ty*& nxt=(mid>=j?node->left:node->right);
    if (nxt==NULL){
        nxt=new Ty(j,j);
        nxt->val=val;
    }
    else if (j>=nxt->l&&j<=nxt->r)
        update2(nxt,j,val);
    else{
        int l=node->l,r=node->r;
        while (true){
            if ((mid>=j)!=(mid>=nxt->l))
                break;
            if (mid>=j)
                r=mid;
            else
                l=mid+1;
            mid=(l+r)>>1;
        }
        auto tmp=new Ty(l,r);
        if (mid>=nxt->l)
            tmp->left=nxt;
        else
            tmp->right=nxt;
        nxt=tmp;
        update2(nxt,j,val);
    }
    node->val=gcd2((node->left==NULL?0:node->left->val),(node->right==NULL?0:node->right->val));
}
long long get2(Ty* node, int u, int v){
    if (node==NULL||node->l>v||node->r<u)
        return 0;
    if (node->l>=u&&node->r<=v)
        return node->val;
    return gcd2(get2(node->left,u,v),get2(node->right,u,v));
}
void update(Tx* node, int l, int r, int i, int j, long long val){
    if (l==r){
        update2(&node->t,j,val);
        return;
    }
    int mid=(l+r)>>1;
    if (mid>=i){
        if (node->left==NULL)
            node->left=new Tx();
        update(node->left,l,mid,i,j,val);
    }
    else{
        if (node->right==NULL)
            node->right=new Tx();
        update(node->right,mid+1,r,i,j,val);
    }
    update2(&node->t,j,gcd2(node->left?get2(&node->left->t,j,j):0,node->right?get2(&node->right->t,j,j):0));
}
long long get(Tx* node, int l, int r, int i, int j, int u, int v){
    if (node==NULL||l>j||r<i)
        return 0;
    if (l>=i&&r<=j)
        return get2(&node->t,u,v);
    return gcd2(get(node->left,l,(l+r)>>1,i,j,u,v),get(node->right,((l+r)>>1)+1,r,i,j,u,v));
}
void init(int R, int C){
    root=new Tx();
}
void update(int P, int Q, long long K){
    update(root,0,999999999,P,Q,K);
}
long long calculate(int P, int Q, int U, int V){
    return get(root,0,999999999,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 496 ms 34604 KB Output is correct
5 Correct 345 ms 34564 KB Output is correct
6 Correct 541 ms 31824 KB Output is correct
7 Correct 590 ms 31996 KB Output is correct
8 Correct 353 ms 18004 KB Output is correct
9 Correct 576 ms 31752 KB Output is correct
10 Correct 557 ms 31568 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 566 ms 15956 KB Output is correct
13 Correct 942 ms 8744 KB Output is correct
14 Correct 234 ms 1108 KB Output is correct
15 Correct 1061 ms 9604 KB Output is correct
16 Correct 267 ms 16012 KB Output is correct
17 Correct 581 ms 12100 KB Output is correct
18 Correct 1031 ms 16924 KB Output is correct
19 Correct 870 ms 16976 KB Output is correct
20 Correct 820 ms 16324 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 652 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 506 ms 34788 KB Output is correct
13 Correct 344 ms 34628 KB Output is correct
14 Correct 539 ms 31828 KB Output is correct
15 Correct 601 ms 31552 KB Output is correct
16 Correct 357 ms 17932 KB Output is correct
17 Correct 625 ms 31608 KB Output is correct
18 Correct 547 ms 31360 KB Output is correct
19 Correct 589 ms 15856 KB Output is correct
20 Correct 956 ms 8688 KB Output is correct
21 Correct 255 ms 1108 KB Output is correct
22 Correct 1072 ms 9772 KB Output is correct
23 Correct 277 ms 16080 KB Output is correct
24 Correct 589 ms 12192 KB Output is correct
25 Correct 1045 ms 16952 KB Output is correct
26 Correct 888 ms 17160 KB Output is correct
27 Correct 825 ms 16484 KB Output is correct
28 Correct 301 ms 38216 KB Output is correct
29 Correct 896 ms 40808 KB Output is correct
30 Correct 1616 ms 32076 KB Output is correct
31 Correct 1449 ms 25892 KB Output is correct
32 Correct 263 ms 6036 KB Output is correct
33 Correct 333 ms 6568 KB Output is correct
34 Correct 190 ms 36536 KB Output is correct
35 Correct 615 ms 22388 KB Output is correct
36 Correct 1192 ms 38620 KB Output is correct
37 Correct 948 ms 38860 KB Output is correct
38 Correct 977 ms 38228 KB Output is correct
39 Correct 795 ms 30936 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 481 ms 34616 KB Output is correct
13 Correct 352 ms 34652 KB Output is correct
14 Correct 542 ms 31924 KB Output is correct
15 Correct 574 ms 31648 KB Output is correct
16 Correct 365 ms 17920 KB Output is correct
17 Correct 594 ms 31872 KB Output is correct
18 Correct 559 ms 31316 KB Output is correct
19 Correct 586 ms 15960 KB Output is correct
20 Correct 972 ms 9080 KB Output is correct
21 Correct 238 ms 1136 KB Output is correct
22 Correct 1089 ms 9536 KB Output is correct
23 Correct 267 ms 16160 KB Output is correct
24 Correct 595 ms 12264 KB Output is correct
25 Correct 1095 ms 17128 KB Output is correct
26 Correct 901 ms 17444 KB Output is correct
27 Correct 856 ms 16496 KB Output is correct
28 Correct 305 ms 38420 KB Output is correct
29 Correct 910 ms 40784 KB Output is correct
30 Correct 1664 ms 32040 KB Output is correct
31 Correct 1535 ms 25544 KB Output is correct
32 Correct 260 ms 5992 KB Output is correct
33 Correct 337 ms 6672 KB Output is correct
34 Correct 190 ms 35880 KB Output is correct
35 Correct 612 ms 22516 KB Output is correct
36 Correct 1170 ms 38500 KB Output is correct
37 Correct 949 ms 38708 KB Output is correct
38 Correct 923 ms 38008 KB Output is correct
39 Correct 416 ms 81184 KB Output is correct
40 Correct 1475 ms 82176 KB Output is correct
41 Correct 2198 ms 67140 KB Output is correct
42 Correct 1995 ms 52628 KB Output is correct
43 Correct 344 ms 77216 KB Output is correct
44 Correct 315 ms 10624 KB Output is correct
45 Correct 760 ms 35648 KB Output is correct
46 Correct 1612 ms 81340 KB Output is correct
47 Correct 1643 ms 81140 KB Output is correct
48 Correct 1593 ms 80556 KB Output is correct
49 Correct 0 ms 348 KB Output is correct