oj.uz

Submission #1102583

# Submission time Handle Problem Language Result Execution time Memory
1102583 2024-10-18T11:16:12 Z ttamx Game (IOI13_game) C++17
80 / 100
 2440 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[14000000];

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 27 ms 226560 KB Output is correct
2 Correct 27 ms 226632 KB Output is correct
3 Correct 28 ms 226640 KB Output is correct
4 Correct 28 ms 226640 KB Output is correct
5 Correct 28 ms 226656 KB Output is correct
6 Correct 27 ms 226640 KB Output is correct
7 Correct 27 ms 226632 KB Output is correct
8 Correct 28 ms 226632 KB Output is correct
9 Correct 28 ms 226632 KB Output is correct
10 Correct 28 ms 226632 KB Output is correct
11 Correct 28 ms 226640 KB Output is correct
12 Correct 27 ms 226640 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 226656 KB Output is correct
2 Correct 27 ms 226496 KB Output is correct
3 Correct 28 ms 226564 KB Output is correct
4 Correct 334 ms 230476 KB Output is correct
5 Correct 256 ms 230968 KB Output is correct
6 Correct 320 ms 227640 KB Output is correct
7 Correct 338 ms 227292 KB Output is correct
8 Correct 235 ms 228168 KB Output is correct
9 Correct 331 ms 227384 KB Output is correct
10 Correct 285 ms 226932 KB Output is correct
11 Correct 31 ms 226632 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 226632 KB Output is correct
2 Correct 28 ms 226640 KB Output is correct
3 Correct 35 ms 226604 KB Output is correct
4 Correct 28 ms 226632 KB Output is correct
5 Correct 28 ms 226632 KB Output is correct
6 Correct 30 ms 226632 KB Output is correct
7 Correct 30 ms 226636 KB Output is correct
8 Correct 30 ms 226572 KB Output is correct
9 Correct 29 ms 226640 KB Output is correct
10 Correct 31 ms 226640 KB Output is correct
11 Correct 29 ms 226632 KB Output is correct
12 Correct 539 ms 230728 KB Output is correct
13 Correct 776 ms 227172 KB Output is correct
14 Correct 212 ms 227144 KB Output is correct
15 Correct 891 ms 227356 KB Output is correct
16 Correct 153 ms 227400 KB Output is correct
17 Correct 477 ms 227912 KB Output is correct
18 Correct 677 ms 227656 KB Output is correct
19 Correct 612 ms 227816 KB Output is correct
20 Correct 570 ms 227144 KB Output is correct
21 Correct 28 ms 226600 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 226632 KB Output is correct
2 Correct 29 ms 226640 KB Output is correct
3 Correct 29 ms 226632 KB Output is correct
4 Correct 29 ms 226632 KB Output is correct
5 Correct 35 ms 226632 KB Output is correct
6 Correct 29 ms 226640 KB Output is correct
7 Correct 30 ms 226632 KB Output is correct
8 Correct 28 ms 226640 KB Output is correct
9 Correct 31 ms 226632 KB Output is correct
10 Correct 30 ms 226640 KB Output is correct
11 Correct 31 ms 226640 KB Output is correct
12 Correct 346 ms 230472 KB Output is correct
13 Correct 300 ms 230984 KB Output is correct
14 Correct 312 ms 227656 KB Output is correct
15 Correct 334 ms 227400 KB Output is correct
16 Correct 250 ms 228168 KB Output is correct
17 Correct 340 ms 227400 KB Output is correct
18 Correct 290 ms 227012 KB Output is correct
19 Correct 522 ms 230728 KB Output is correct
20 Correct 776 ms 227268 KB Output is correct
21 Correct 206 ms 227144 KB Output is correct
22 Correct 860 ms 227400 KB Output is correct
23 Correct 137 ms 227164 KB Output is correct
24 Correct 465 ms 227912 KB Output is correct
25 Correct 679 ms 227532 KB Output is correct
26 Correct 619 ms 227792 KB Output is correct
27 Correct 595 ms 227144 KB Output is correct
28 Correct 385 ms 227144 KB Output is correct
29 Correct 891 ms 230592 KB Output is correct
30 Correct 2425 ms 227084 KB Output is correct
31 Correct 2299 ms 227168 KB Output is correct
32 Correct 351 ms 227120 KB Output is correct
33 Correct 452 ms 227168 KB Output is correct
34 Correct 244 ms 227396 KB Output is correct
35 Correct 667 ms 227796 KB Output is correct
36 Correct 1094 ms 227668 KB Output is correct
37 Correct 996 ms 227656 KB Output is correct
38 Correct 878 ms 227144 KB Output is correct
39 Correct 732 ms 227716 KB Output is correct
40 Correct 29 ms 226556 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 226632 KB Output is correct
2 Correct 28 ms 226640 KB Output is correct
3 Correct 27 ms 226640 KB Output is correct
4 Correct 27 ms 226640 KB Output is correct
5 Correct 27 ms 226632 KB Output is correct
6 Correct 27 ms 226524 KB Output is correct
7 Correct 27 ms 226640 KB Output is correct
8 Correct 27 ms 226652 KB Output is correct
9 Correct 27 ms 226632 KB Output is correct
10 Correct 28 ms 226632 KB Output is correct
11 Correct 27 ms 226676 KB Output is correct
12 Correct 328 ms 230516 KB Output is correct
13 Correct 246 ms 230772 KB Output is correct
14 Correct 325 ms 227580 KB Output is correct
15 Correct 344 ms 227400 KB Output is correct
16 Correct 254 ms 228184 KB Output is correct
17 Correct 339 ms 227400 KB Output is correct
18 Correct 289 ms 227144 KB Output is correct
19 Correct 567 ms 230728 KB Output is correct
20 Correct 782 ms 227144 KB Output is correct
21 Correct 199 ms 227164 KB Output is correct
22 Correct 875 ms 227144 KB Output is correct
23 Correct 135 ms 227400 KB Output is correct
24 Correct 506 ms 227924 KB Output is correct
25 Correct 702 ms 227676 KB Output is correct
26 Correct 618 ms 227768 KB Output is correct
27 Correct 556 ms 227144 KB Output is correct
28 Correct 365 ms 227208 KB Output is correct
29 Correct 868 ms 230216 KB Output is correct
30 Correct 2440 ms 227180 KB Output is correct
31 Correct 2319 ms 227376 KB Output is correct
32 Correct 351 ms 227144 KB Output is correct
33 Correct 456 ms 227144 KB Output is correct
34 Correct 229 ms 227160 KB Output is correct
35 Correct 603 ms 227912 KB Output is correct
36 Correct 1138 ms 227604 KB Output is correct
37 Correct 991 ms 228056 KB Output is correct
38 Correct 917 ms 227248 KB Output is correct
39 Runtime error 663 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -