oj.uz

Submission #1102579

# Submission time Handle Problem Language Result Execution time Memory
1102579 2024-10-18T11:08:20 Z ttamx Game (IOI13_game) C++17
80 / 100
 2356 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

int n,m;

struct Node{
    ll val;
    int l,r;
    Node():val(0LL),l(0),r(0){}
}node[10000000];

int cur_node=0;

struct SegTree{
    int root;
    SegTree():root(0){}
    ll get(int t){
        return t?node[t].val:0LL;
    }
    void modify(int l,int r,int &t,int x,ll v){
        if(!t)t=++cur_node;
        if(l==r)return void(node[t].val=v);
        int m=(l+r)/2;
        if(x<=m)modify(l,m,node[t].l,x,v);
        else modify(m+1,r,node[t].r,x,v);
        node[t].val=gcd2(get(node[t].l),get(node[t].r));
    }
    void modify(int x,ll v){
        modify(0,m-1,root,x,v);
    }
    ll query(int l,int r,int &t,int x,int y){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].val;
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y),query(m+1,r,node[t].r,x,y));
    }
    ll query(int x,int y){
        return query(0,m-1,root,x,y);
    }
};

struct SegTree2D{
    struct Node;
    using Ptr = Node*;
    struct Node{
        SegTree tree;
        Ptr l,r;
        Node():tree(),l(),r(){}
    };
    Ptr root;
    SegTree2D():root(){}
    ll get(Ptr t,int x){
        return t?t->tree.query(x,x):0LL;
    }
    void modify(int l,int r,Ptr &t,int x,int y,ll v){
        if(!t)t=new Node();
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,t->l,x,y,v);
            else modify(m+1,r,t->r,x,y,v);
            v=gcd2(get(t->l,y),get(t->r,y));
        }
        t->tree.modify(y,v);
    }
    void modify(int x,int y,ll v){
        modify(0,n-1,root,x,y,v);
    }
    ll query(int l,int r,Ptr &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return t->tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,t->l,x,y,x2,y2),query(m+1,r,t->r,x,y,x2,y2));
    }
    ll query(int x,int y,int x2,int y2){
        return query(0,n-1,root,x,y,x2,y2);
    }
}seg;

void init(int R,int C){
    n=R,m=C;
}

void update(int P,int Q,ll K){
    seg.modify(P,Q,K);
}

ll calculate(int P,int Q,int U,int V){
    return seg.query(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 156752 KB Output is correct
2 Correct 22 ms 157172 KB Output is correct
3 Correct 23 ms 156752 KB Output is correct
4 Correct 20 ms 156752 KB Output is correct
5 Correct 21 ms 156764 KB Output is correct
6 Correct 21 ms 156764 KB Output is correct
7 Correct 21 ms 156920 KB Output is correct
8 Correct 22 ms 156752 KB Output is correct
9 Correct 23 ms 156764 KB Output is correct
10 Correct 21 ms 156744 KB Output is correct
11 Correct 21 ms 156752 KB Output is correct
12 Correct 23 ms 156752 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 156744 KB Output is correct
2 Correct 21 ms 156752 KB Output is correct
3 Correct 21 ms 156812 KB Output is correct
4 Correct 326 ms 160888 KB Output is correct
5 Correct 231 ms 161352 KB Output is correct
6 Correct 312 ms 158024 KB Output is correct
7 Correct 299 ms 157852 KB Output is correct
8 Correct 218 ms 158540 KB Output is correct
9 Correct 290 ms 157864 KB Output is correct
10 Correct 263 ms 157256 KB Output is correct
11 Correct 21 ms 156752 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 157008 KB Output is correct
2 Correct 22 ms 156792 KB Output is correct
3 Correct 23 ms 156996 KB Output is correct
4 Correct 22 ms 156896 KB Output is correct
5 Correct 22 ms 156752 KB Output is correct
6 Correct 21 ms 156748 KB Output is correct
7 Correct 20 ms 156752 KB Output is correct
8 Correct 22 ms 156764 KB Output is correct
9 Correct 21 ms 156752 KB Output is correct
10 Correct 21 ms 157008 KB Output is correct
11 Correct 24 ms 156744 KB Output is correct
12 Correct 515 ms 161036 KB Output is correct
13 Correct 755 ms 157556 KB Output is correct
14 Correct 192 ms 157512 KB Output is correct
15 Correct 864 ms 157672 KB Output is correct
16 Correct 131 ms 157768 KB Output is correct
17 Correct 513 ms 158272 KB Output is correct
18 Correct 760 ms 158028 KB Output is correct
19 Correct 646 ms 158188 KB Output is correct
20 Correct 616 ms 157512 KB Output is correct
21 Correct 21 ms 156744 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 156752 KB Output is correct
2 Correct 20 ms 156752 KB Output is correct
3 Correct 22 ms 156984 KB Output is correct
4 Correct 21 ms 156752 KB Output is correct
5 Correct 21 ms 156752 KB Output is correct
6 Correct 21 ms 157008 KB Output is correct
7 Correct 21 ms 156752 KB Output is correct
8 Correct 22 ms 157008 KB Output is correct
9 Correct 21 ms 156784 KB Output is correct
10 Correct 22 ms 156804 KB Output is correct
11 Correct 21 ms 156768 KB Output is correct
12 Correct 321 ms 160840 KB Output is correct
13 Correct 216 ms 161096 KB Output is correct
14 Correct 343 ms 158024 KB Output is correct
15 Correct 294 ms 157768 KB Output is correct
16 Correct 219 ms 158536 KB Output is correct
17 Correct 307 ms 157820 KB Output is correct
18 Correct 288 ms 157256 KB Output is correct
19 Correct 514 ms 161100 KB Output is correct
20 Correct 739 ms 157692 KB Output is correct
21 Correct 196 ms 157448 KB Output is correct
22 Correct 848 ms 157712 KB Output is correct
23 Correct 131 ms 157768 KB Output is correct
24 Correct 498 ms 158340 KB Output is correct
25 Correct 733 ms 158012 KB Output is correct
26 Correct 672 ms 158284 KB Output is correct
27 Correct 594 ms 157512 KB Output is correct
28 Correct 386 ms 162888 KB Output is correct
29 Correct 875 ms 176084 KB Output is correct
30 Correct 2344 ms 167500 KB Output is correct
31 Correct 2265 ms 166896 KB Output is correct
32 Correct 364 ms 166744 KB Output is correct
33 Correct 473 ms 166548 KB Output is correct
34 Correct 255 ms 170060 KB Output is correct
35 Correct 655 ms 170844 KB Output is correct
36 Correct 1147 ms 173944 KB Output is correct
37 Correct 953 ms 174256 KB Output is correct
38 Correct 903 ms 173684 KB Output is correct
39 Correct 764 ms 172592 KB Output is correct
40 Correct 20 ms 156996 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 157144 KB Output is correct
2 Correct 19 ms 156752 KB Output is correct
3 Correct 19 ms 156752 KB Output is correct
4 Correct 20 ms 156752 KB Output is correct
5 Correct 19 ms 156752 KB Output is correct
6 Correct 19 ms 157008 KB Output is correct
7 Correct 19 ms 156796 KB Output is correct
8 Correct 19 ms 156752 KB Output is correct
9 Correct 22 ms 156752 KB Output is correct
10 Correct 19 ms 156744 KB Output is correct
11 Correct 19 ms 156752 KB Output is correct
12 Correct 306 ms 161008 KB Output is correct
13 Correct 219 ms 161352 KB Output is correct
14 Correct 314 ms 158020 KB Output is correct
15 Correct 324 ms 157768 KB Output is correct
16 Correct 231 ms 158536 KB Output is correct
17 Correct 332 ms 157768 KB Output is correct
18 Correct 274 ms 157480 KB Output is correct
19 Correct 506 ms 161096 KB Output is correct
20 Correct 775 ms 157768 KB Output is correct
21 Correct 198 ms 157348 KB Output is correct
22 Correct 889 ms 157772 KB Output is correct
23 Correct 136 ms 157852 KB Output is correct
24 Correct 528 ms 158280 KB Output is correct
25 Correct 734 ms 158024 KB Output is correct
26 Correct 608 ms 158280 KB Output is correct
27 Correct 552 ms 157700 KB Output is correct
28 Correct 337 ms 162888 KB Output is correct
29 Correct 819 ms 176200 KB Output is correct
30 Correct 2356 ms 167512 KB Output is correct
31 Correct 2253 ms 166868 KB Output is correct
32 Correct 375 ms 166584 KB Output is correct
33 Correct 462 ms 166732 KB Output is correct
34 Correct 260 ms 170060 KB Output is correct
35 Correct 677 ms 170832 KB Output is correct
36 Correct 1025 ms 174132 KB Output is correct
37 Correct 921 ms 174112 KB Output is correct
38 Correct 882 ms 173644 KB Output is correct
39 Runtime error 704 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -