oj.uz

Submission #1102570

# Submission time Handle Problem Language Result Execution time Memory
1102570 2024-10-18T10:41:12 Z ttamx Game (IOI13_game) C++17
63 / 100
 1145 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 SegTree{
    struct Node;
    using Ptr = Node*;
    struct Node{
        ll val;
        Ptr l,r;
        Node():val(0LL),l(),r(){}
    };
    Ptr root;
    SegTree():root(){}
    ll get(Ptr t){
        return t?t->val:0LL;
    }
    void modify(int l,int r,Ptr &t,int x,ll v){
        if(!t)t=new Node();
        if(l==r)return void(t->val=v);
        int m=(l+r)/2;
        if(x<=m)modify(l,m,t->l,x,v);
        else modify(m+1,r,t->r,x,v);
        t->val=gcd2(get(t->l),get(t->r));
    }
    void modify(int x,ll v){
        modify(0,1e9,root,x,v);
    }
    ll query(int l,int r,Ptr &t,int x,int y){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return t->val;
        int m=(l+r)/2;
        return gcd2(query(l,m,t->l,x,y),query(m+1,r,t->r,x,y));
    }
    ll query(int x,int y){
        return query(0,1e9,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,1e9,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,1e9,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 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 764 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 501 ms 54876 KB Output is correct
5 Correct 428 ms 54256 KB Output is correct
6 Correct 532 ms 52044 KB Output is correct
7 Correct 556 ms 51788 KB Output is correct
8 Correct 363 ms 33100 KB Output is correct
9 Correct 529 ms 52176 KB Output is correct
10 Correct 505 ms 51644 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 820 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 781 ms 22732 KB Output is correct
13 Correct 984 ms 12836 KB Output is correct
14 Correct 361 ms 5964 KB Output is correct
15 Correct 1115 ms 17964 KB Output is correct
16 Correct 383 ms 27724 KB Output is correct
17 Correct 762 ms 21216 KB Output is correct
18 Correct 1073 ms 28996 KB Output is correct
19 Correct 1020 ms 29240 KB Output is correct
20 Correct 992 ms 28492 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 760 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 513 ms 54596 KB Output is correct
13 Correct 412 ms 54404 KB Output is correct
14 Correct 514 ms 52112 KB Output is correct
15 Correct 563 ms 51828 KB Output is correct
16 Correct 386 ms 32968 KB Output is correct
17 Correct 546 ms 52280 KB Output is correct
18 Correct 516 ms 51780 KB Output is correct
19 Correct 788 ms 22660 KB Output is correct
20 Correct 999 ms 12776 KB Output is correct
21 Correct 367 ms 5964 KB Output is correct
22 Correct 1130 ms 17900 KB Output is correct
23 Correct 383 ms 27724 KB Output is correct
24 Correct 744 ms 21068 KB Output is correct
25 Correct 1145 ms 29004 KB Output is correct
26 Correct 1027 ms 29164 KB Output is correct
27 Correct 972 ms 28540 KB Output is correct
28 Correct 636 ms 256000 KB Output is correct
29 Runtime error 1106 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 1 ms 336 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 508 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 519 ms 54676 KB Output is correct
13 Correct 413 ms 54388 KB Output is correct
14 Correct 526 ms 52224 KB Output is correct
15 Correct 580 ms 51788 KB Output is correct
16 Correct 396 ms 33100 KB Output is correct
17 Correct 581 ms 52300 KB Output is correct
18 Correct 524 ms 51792 KB Output is correct
19 Correct 781 ms 22740 KB Output is correct
20 Correct 982 ms 12920 KB Output is correct
21 Correct 370 ms 5964 KB Output is correct
22 Correct 1143 ms 17884 KB Output is correct
23 Correct 404 ms 27728 KB Output is correct
24 Correct 770 ms 21116 KB Output is correct
25 Correct 1131 ms 28940 KB Output is correct
26 Correct 1036 ms 29228 KB Output is correct
27 Correct 1012 ms 28636 KB Output is correct
28 Correct 675 ms 256000 KB Output is correct
29 Runtime error 1081 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -