oj.uz

Submission #1102582

# Submission time Handle Problem Language Result Execution time Memory
1102582 2024-10-18T11:14:42 Z ttamx Game (IOI13_game) C++17
80 / 100
 2451 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{
        SegTree tree;
        int l,r;
        Node():tree(),l(),r(){}
    }node[600000];
    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 23 ms 163920 KB Output is correct
2 Correct 23 ms 163784 KB Output is correct
3 Correct 24 ms 163912 KB Output is correct
4 Correct 22 ms 163920 KB Output is correct
5 Correct 21 ms 163920 KB Output is correct
6 Correct 21 ms 163920 KB Output is correct
7 Correct 21 ms 163920 KB Output is correct
8 Correct 21 ms 163792 KB Output is correct
9 Correct 21 ms 163924 KB Output is correct
10 Correct 21 ms 163920 KB Output is correct
11 Correct 21 ms 163920 KB Output is correct
12 Correct 20 ms 163920 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 163920 KB Output is correct
2 Correct 20 ms 163940 KB Output is correct
3 Correct 20 ms 163920 KB Output is correct
4 Correct 314 ms 168096 KB Output is correct
5 Correct 239 ms 168264 KB Output is correct
6 Correct 282 ms 164944 KB Output is correct
7 Correct 297 ms 164840 KB Output is correct
8 Correct 236 ms 165620 KB Output is correct
9 Correct 328 ms 164936 KB Output is correct
10 Correct 300 ms 164424 KB Output is correct
11 Correct 22 ms 163912 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 163912 KB Output is correct
2 Correct 25 ms 163912 KB Output is correct
3 Correct 23 ms 164000 KB Output is correct
4 Correct 24 ms 163904 KB Output is correct
5 Correct 23 ms 163920 KB Output is correct
6 Correct 22 ms 163924 KB Output is correct
7 Correct 26 ms 164092 KB Output is correct
8 Correct 24 ms 163912 KB Output is correct
9 Correct 22 ms 163912 KB Output is correct
10 Correct 24 ms 163920 KB Output is correct
11 Correct 23 ms 163920 KB Output is correct
12 Correct 542 ms 167964 KB Output is correct
13 Correct 785 ms 164644 KB Output is correct
14 Correct 217 ms 164424 KB Output is correct
15 Correct 882 ms 164680 KB Output is correct
16 Correct 136 ms 164548 KB Output is correct
17 Correct 471 ms 165204 KB Output is correct
18 Correct 664 ms 165076 KB Output is correct
19 Correct 609 ms 165192 KB Output is correct
20 Correct 555 ms 164396 KB Output is correct
21 Correct 20 ms 163920 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 163964 KB Output is correct
2 Correct 21 ms 163932 KB Output is correct
3 Correct 23 ms 163920 KB Output is correct
4 Correct 28 ms 163920 KB Output is correct
5 Correct 23 ms 163960 KB Output is correct
6 Correct 23 ms 163792 KB Output is correct
7 Correct 27 ms 163920 KB Output is correct
8 Correct 23 ms 163952 KB Output is correct
9 Correct 22 ms 163920 KB Output is correct
10 Correct 22 ms 163920 KB Output is correct
11 Correct 23 ms 163920 KB Output is correct
12 Correct 355 ms 168008 KB Output is correct
13 Correct 246 ms 168376 KB Output is correct
14 Correct 290 ms 164936 KB Output is correct
15 Correct 297 ms 164744 KB Output is correct
16 Correct 234 ms 165448 KB Output is correct
17 Correct 320 ms 164904 KB Output is correct
18 Correct 304 ms 164424 KB Output is correct
19 Correct 529 ms 167948 KB Output is correct
20 Correct 760 ms 164680 KB Output is correct
21 Correct 198 ms 164424 KB Output is correct
22 Correct 868 ms 164552 KB Output is correct
23 Correct 123 ms 164680 KB Output is correct
24 Correct 460 ms 165324 KB Output is correct
25 Correct 715 ms 164928 KB Output is correct
26 Correct 670 ms 165104 KB Output is correct
27 Correct 618 ms 164424 KB Output is correct
28 Correct 380 ms 164512 KB Output is correct
29 Correct 918 ms 167596 KB Output is correct
30 Correct 2451 ms 164624 KB Output is correct
31 Correct 2302 ms 164768 KB Output is correct
32 Correct 369 ms 164412 KB Output is correct
33 Correct 489 ms 164440 KB Output is correct
34 Correct 252 ms 164684 KB Output is correct
35 Correct 651 ms 165336 KB Output is correct
36 Correct 1090 ms 164908 KB Output is correct
37 Correct 910 ms 165192 KB Output is correct
38 Correct 920 ms 164624 KB Output is correct
39 Correct 789 ms 165192 KB Output is correct
40 Correct 21 ms 163920 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 163920 KB Output is correct
2 Correct 21 ms 163920 KB Output is correct
3 Correct 25 ms 163920 KB Output is correct
4 Correct 21 ms 163920 KB Output is correct
5 Correct 20 ms 163920 KB Output is correct
6 Correct 21 ms 163920 KB Output is correct
7 Correct 21 ms 164012 KB Output is correct
8 Correct 21 ms 163912 KB Output is correct
9 Correct 21 ms 163920 KB Output is correct
10 Correct 21 ms 163920 KB Output is correct
11 Correct 23 ms 163920 KB Output is correct
12 Correct 322 ms 168008 KB Output is correct
13 Correct 220 ms 168264 KB Output is correct
14 Correct 282 ms 164924 KB Output is correct
15 Correct 300 ms 164808 KB Output is correct
16 Correct 240 ms 165456 KB Output is correct
17 Correct 335 ms 164936 KB Output is correct
18 Correct 291 ms 164552 KB Output is correct
19 Correct 548 ms 168008 KB Output is correct
20 Correct 757 ms 164608 KB Output is correct
21 Correct 196 ms 164548 KB Output is correct
22 Correct 911 ms 164680 KB Output is correct
23 Correct 145 ms 164680 KB Output is correct
24 Correct 499 ms 165300 KB Output is correct
25 Correct 750 ms 165084 KB Output is correct
26 Correct 625 ms 165192 KB Output is correct
27 Correct 587 ms 164584 KB Output is correct
28 Correct 378 ms 164552 KB Output is correct
29 Correct 858 ms 167680 KB Output is correct
30 Correct 2443 ms 164360 KB Output is correct
31 Correct 2361 ms 164532 KB Output is correct
32 Correct 362 ms 164424 KB Output is correct
33 Correct 514 ms 164424 KB Output is correct
34 Correct 243 ms 164680 KB Output is correct
35 Correct 612 ms 165192 KB Output is correct
36 Correct 998 ms 164852 KB Output is correct
37 Correct 861 ms 165192 KB Output is correct
38 Correct 903 ms 164528 KB Output is correct
39 Runtime error 770 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -