oj.uz

Submission #1102581

# Submission time Handle Problem Language Result Execution time Memory
1102581 2024-10-18T11:13:41 Z ttamx Game (IOI13_game) C++17
63 / 100
 1422 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[8000000];

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{
        SegTree tree;
        int l,r;
        Node():tree(),l(),r(){}
    }node[800000];
    int root,cur_node;
    SegTree2D():root(0),cur_node(0){}
    ll get(int t,int x){
        return t?node[t].tree.query(x,x):0LL;
    }
    void modify(int l,int r,int &t,int x,int y,ll v){
        if(!t)t=++cur_node;
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,node[t].l,x,y,v);
            else modify(m+1,r,node[t].r,x,y,v);
            v=gcd2(get(node[t].l,y),get(node[t].r,y));
        }
        node[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,int &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return node[t].tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,node[t].l,x,y,x2,y2),query(m+1,r,node[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 18 ms 134992 KB Output is correct
2 Correct 17 ms 134992 KB Output is correct
3 Correct 17 ms 134992 KB Output is correct
4 Correct 20 ms 134992 KB Output is correct
5 Correct 19 ms 134992 KB Output is correct
6 Correct 19 ms 135044 KB Output is correct
7 Correct 19 ms 134992 KB Output is correct
8 Correct 19 ms 134992 KB Output is correct
9 Correct 19 ms 134992 KB Output is correct
10 Correct 19 ms 134992 KB Output is correct
11 Correct 17 ms 134992 KB Output is correct
12 Correct 17 ms 135004 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 134992 KB Output is correct
2 Correct 20 ms 135004 KB Output is correct
3 Correct 17 ms 134992 KB Output is correct
4 Correct 310 ms 139080 KB Output is correct
5 Correct 217 ms 139308 KB Output is correct
6 Correct 274 ms 136008 KB Output is correct
7 Correct 294 ms 135752 KB Output is correct
8 Correct 221 ms 136520 KB Output is correct
9 Correct 290 ms 135760 KB Output is correct
10 Correct 279 ms 135512 KB Output is correct
11 Correct 18 ms 134992 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 134992 KB Output is correct
2 Correct 19 ms 135160 KB Output is correct
3 Correct 19 ms 134876 KB Output is correct
4 Correct 19 ms 134992 KB Output is correct
5 Correct 19 ms 134992 KB Output is correct
6 Correct 21 ms 134992 KB Output is correct
7 Correct 20 ms 135060 KB Output is correct
8 Correct 18 ms 134992 KB Output is correct
9 Correct 24 ms 134992 KB Output is correct
10 Correct 19 ms 134992 KB Output is correct
11 Correct 19 ms 134992 KB Output is correct
12 Correct 533 ms 139080 KB Output is correct
13 Correct 764 ms 135696 KB Output is correct
14 Correct 193 ms 135424 KB Output is correct
15 Correct 916 ms 135688 KB Output is correct
16 Correct 122 ms 135752 KB Output is correct
17 Correct 483 ms 136264 KB Output is correct
18 Correct 755 ms 136112 KB Output is correct
19 Correct 609 ms 136064 KB Output is correct
20 Correct 611 ms 135496 KB Output is correct
21 Correct 17 ms 134992 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 134992 KB Output is correct
2 Correct 17 ms 135160 KB Output is correct
3 Correct 18 ms 134992 KB Output is correct
4 Correct 17 ms 134992 KB Output is correct
5 Correct 17 ms 134992 KB Output is correct
6 Correct 17 ms 134988 KB Output is correct
7 Correct 17 ms 134992 KB Output is correct
8 Correct 17 ms 134992 KB Output is correct
9 Correct 17 ms 134992 KB Output is correct
10 Correct 18 ms 134992 KB Output is correct
11 Correct 18 ms 134992 KB Output is correct
12 Correct 333 ms 139080 KB Output is correct
13 Correct 238 ms 139336 KB Output is correct
14 Correct 350 ms 135964 KB Output is correct
15 Correct 326 ms 135836 KB Output is correct
16 Correct 231 ms 136520 KB Output is correct
17 Correct 308 ms 135788 KB Output is correct
18 Correct 277 ms 135496 KB Output is correct
19 Correct 518 ms 139080 KB Output is correct
20 Correct 770 ms 135592 KB Output is correct
21 Correct 188 ms 135496 KB Output is correct
22 Correct 876 ms 135792 KB Output is correct
23 Correct 123 ms 135752 KB Output is correct
24 Correct 480 ms 136316 KB Output is correct
25 Correct 695 ms 136056 KB Output is correct
26 Correct 613 ms 136028 KB Output is correct
27 Correct 586 ms 135496 KB Output is correct
28 Correct 352 ms 135496 KB Output is correct
29 Runtime error 1309 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 134964 KB Output is correct
2 Correct 19 ms 135060 KB Output is correct
3 Correct 18 ms 134992 KB Output is correct
4 Correct 19 ms 134992 KB Output is correct
5 Correct 19 ms 134992 KB Output is correct
6 Correct 19 ms 134992 KB Output is correct
7 Correct 18 ms 134992 KB Output is correct
8 Correct 18 ms 134992 KB Output is correct
9 Correct 18 ms 134992 KB Output is correct
10 Correct 19 ms 135056 KB Output is correct
11 Correct 19 ms 134992 KB Output is correct
12 Correct 326 ms 138888 KB Output is correct
13 Correct 228 ms 139432 KB Output is correct
14 Correct 289 ms 135984 KB Output is correct
15 Correct 347 ms 135796 KB Output is correct
16 Correct 263 ms 136520 KB Output is correct
17 Correct 328 ms 135908 KB Output is correct
18 Correct 260 ms 135548 KB Output is correct
19 Correct 506 ms 139080 KB Output is correct
20 Correct 748 ms 135580 KB Output is correct
21 Correct 216 ms 135496 KB Output is correct
22 Correct 860 ms 135808 KB Output is correct
23 Correct 130 ms 135752 KB Output is correct
24 Correct 505 ms 136416 KB Output is correct
25 Correct 761 ms 136020 KB Output is correct
26 Correct 647 ms 136008 KB Output is correct
27 Correct 608 ms 135496 KB Output is correct
28 Correct 374 ms 135496 KB Output is correct
29 Runtime error 1422 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -