oj.uz

Submission #1032107

# Submission time Handle Problem Language Result Execution time Memory
1032107 2024-07-23T11:46:33 Z noyancanturk Game (IOI13_game) C++17
80 / 100
 1489 ms 256000 KB 
#include "game.h"

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;
}

#include<iostream>
struct Nd{
    long long val=0;
    int ch[2]{0,0};
}tree[15000000];
int nx=1;
int L,R;
long long ANS;
int n,m;
int P;
long long VAL;
struct segtree {
    int root;
    void update(int l,int r,int&node){
        if(!node){
            node=nx++;
        }
        if(l==r){
            tree[node].val=VAL;
            return;
        }
        int mid=(l+r)>>1;
        if(P<=mid){
            update(l,mid,tree[node].ch[0]);
        }else{
            update(mid+1,r,tree[node].ch[1]);
        }
        tree[node].val=gcd2(tree[tree[node].ch[0]].val,tree[tree[node].ch[1]].val);
    }
    void update(int p,long long val){
        P=p;
        update(0,m-1,root);
    }
    void insert(int l,int r,int&node,int node1,int node2){
        if(!node){
            node=nx++;
        }
        tree[node].val=gcd2(tree[node1].val,tree[node2].val);
        if(l==r)return;
        int mid=(l+r)>>1;
        if(P<=mid){
            insert(l,mid,tree[node].ch[0],tree[node1].ch[0],tree[node2].ch[0]);
        }else{
            insert(mid+1,r,tree[node].ch[1],tree[node1].ch[1],tree[node2].ch[1]);
        }
    }
    void insert(int p,int node1,int node2){
        P=p;
        insert(0,m-1,root,node1,node2);
    }
    void query(int l,int r,int node){
        if(L<=l&r<=R){
            ANS=gcd2(ANS,tree[node].val);
            return;
        }
        if(r<L||R<l)return;
        int mid=(l+r)>>1;
        if(tree[node].ch[0])query(l,mid,tree[node].ch[0]);
        if(tree[node].ch[1])query(mid+1,r,tree[node].ch[1]);
    }
    void query(int l,int r){
        L=l,R=r;
        query(0,m-1,root);
    }
};

struct {
    struct {
        segtree sst;
        int ch[2]{0,0};
    }subtree[1000000];
    int nxx=1;
    void init(int N,int M){
        n=N,m=M;
    }
    int P1,P2;
    void update(int l,int r,int&node){
        if(!node){
            node=++nxx;
        }
        if(l==r){
            subtree[node].sst.update(P2,VAL);
            return;
        }
        int mid=(l+r)>>1;
        if(P1<=mid){
            update(l,mid,subtree[node].ch[0]);
        }else{
            update(mid+1,r,subtree[node].ch[1]);
        }
        subtree[node].sst.insert(P2,subtree[subtree[node].ch[0]].sst.root,subtree[subtree[node].ch[1]].sst.root);
    }
    void update(int p1,int p2,long long val){
        P1=p1,P2=p2,VAL=val;
        int root=1;
        update(0,n-1,root);
    }
    int L1,R1,L2,R2;
    void query(int l,int r,int node){
        if(L1<=l&&r<=R1){
            subtree[node].sst.query(L2,R2);
            return;
        }
        if(r<L1||R1<l)return;
        int mid=(l+r)>>1;
        if(subtree[node].ch[0])query(l,mid,subtree[node].ch[0]);
        if(subtree[node].ch[1])query(mid+1,r,subtree[node].ch[1]);
    }
    long long query(int l1,int r1,int l2,int r2){
        L1=l1,R1=r1,L2=l2,R2=r2;
        ANS=0;
        query(0,n-1,1);
        return ANS;
    }
}st;

void init(int R, int C) {
    st.init(R,C);
}

void update(int P, int Q, long long K) {
    st.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    long long val=st.query(P,U,Q,V);
    return val;
}

Compilation message

game.cpp: In member function 'void segtree::query(int, int, int)':
game.cpp:64:13: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   64 |         if(L<=l&r<=R){
      |            ~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12888 KB Output is correct
2 Correct 5 ms 12892 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12892 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 3 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12800 KB Output is correct
11 Correct 4 ms 12756 KB Output is correct
12 Correct 4 ms 12916 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12888 KB Output is correct
2 Correct 4 ms 12892 KB Output is correct
3 Correct 4 ms 12864 KB Output is correct
4 Correct 265 ms 20948 KB Output is correct
5 Correct 178 ms 21332 KB Output is correct
6 Correct 222 ms 18028 KB Output is correct
7 Correct 249 ms 18008 KB Output is correct
8 Correct 193 ms 16720 KB Output is correct
9 Correct 290 ms 18044 KB Output is correct
10 Correct 221 ms 17488 KB Output is correct
11 Correct 4 ms 13144 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 4 ms 12952 KB Output is correct
3 Correct 5 ms 12888 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 6 ms 12892 KB Output is correct
8 Correct 4 ms 12888 KB Output is correct
9 Correct 4 ms 12868 KB Output is correct
10 Correct 6 ms 12892 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 402 ms 22612 KB Output is correct
13 Correct 588 ms 15956 KB Output is correct
14 Correct 139 ms 13496 KB Output is correct
15 Correct 611 ms 17200 KB Output is correct
16 Correct 97 ms 22100 KB Output is correct
17 Correct 390 ms 19080 KB Output is correct
18 Correct 527 ms 22356 KB Output is correct
19 Correct 530 ms 22660 KB Output is correct
20 Correct 461 ms 21844 KB Output is correct
21 Correct 4 ms 12892 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 4 ms 12768 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 5 ms 12892 KB Output is correct
7 Correct 5 ms 12748 KB Output is correct
8 Correct 4 ms 12892 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12764 KB Output is correct
11 Correct 4 ms 12888 KB Output is correct
12 Correct 257 ms 21028 KB Output is correct
13 Correct 187 ms 21328 KB Output is correct
14 Correct 229 ms 18000 KB Output is correct
15 Correct 304 ms 17748 KB Output is correct
16 Correct 188 ms 16752 KB Output is correct
17 Correct 233 ms 18032 KB Output is correct
18 Correct 257 ms 17480 KB Output is correct
19 Correct 402 ms 22612 KB Output is correct
20 Correct 531 ms 16136 KB Output is correct
21 Correct 184 ms 13392 KB Output is correct
22 Correct 599 ms 17376 KB Output is correct
23 Correct 97 ms 22096 KB Output is correct
24 Correct 405 ms 19236 KB Output is correct
25 Correct 501 ms 22352 KB Output is correct
26 Correct 492 ms 22560 KB Output is correct
27 Correct 457 ms 21840 KB Output is correct
28 Correct 295 ms 136020 KB Output is correct
29 Correct 759 ms 151068 KB Output is correct
30 Correct 1489 ms 113236 KB Output is correct
31 Correct 1416 ms 89580 KB Output is correct
32 Correct 263 ms 13648 KB Output is correct
33 Correct 317 ms 14672 KB Output is correct
34 Correct 190 ms 148248 KB Output is correct
35 Correct 479 ms 81748 KB Output is correct
36 Correct 930 ms 148560 KB Output is correct
37 Correct 700 ms 148760 KB Output is correct
38 Correct 736 ms 148176 KB Output is correct
39 Correct 612 ms 117072 KB Output is correct
40 Correct 4 ms 12888 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 7 ms 12720 KB Output is correct
3 Correct 4 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 4 ms 12892 KB Output is correct
6 Correct 4 ms 12740 KB Output is correct
7 Correct 4 ms 12892 KB Output is correct
8 Correct 4 ms 12888 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 4 ms 12792 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 268 ms 21040 KB Output is correct
13 Correct 174 ms 21328 KB Output is correct
14 Correct 284 ms 18076 KB Output is correct
15 Correct 283 ms 17748 KB Output is correct
16 Correct 184 ms 16720 KB Output is correct
17 Correct 242 ms 17920 KB Output is correct
18 Correct 233 ms 17488 KB Output is correct
19 Correct 421 ms 22616 KB Output is correct
20 Correct 528 ms 15952 KB Output is correct
21 Correct 146 ms 13392 KB Output is correct
22 Correct 600 ms 17228 KB Output is correct
23 Correct 109 ms 22048 KB Output is correct
24 Correct 420 ms 19032 KB Output is correct
25 Correct 545 ms 22460 KB Output is correct
26 Correct 467 ms 22608 KB Output is correct
27 Correct 437 ms 22204 KB Output is correct
28 Correct 327 ms 136020 KB Output is correct
29 Correct 687 ms 151172 KB Output is correct
30 Correct 1462 ms 113232 KB Output is correct
31 Correct 1489 ms 89508 KB Output is correct
32 Correct 197 ms 13392 KB Output is correct
33 Correct 319 ms 14676 KB Output is correct
34 Correct 195 ms 148204 KB Output is correct
35 Correct 505 ms 81748 KB Output is correct
36 Correct 952 ms 148564 KB Output is correct
37 Correct 743 ms 148620 KB Output is correct
38 Correct 732 ms 148052 KB Output is correct
39 Runtime error 422 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -