oj.uz

Submission #1102571

# Submission time Handle Problem Language Result Execution time Memory
1102571 2024-10-18T10:42:43 Z ttamx Game (IOI13_game) C++17
63 / 100
 1121 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,m-1,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,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 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 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 336 KB Output is correct
4 Correct 298 ms 12580 KB Output is correct
5 Correct 212 ms 12872 KB Output is correct
6 Correct 277 ms 9800 KB Output is correct
7 Correct 290 ms 9544 KB Output is correct
8 Correct 206 ms 6728 KB Output is correct
9 Correct 286 ms 9800 KB Output is correct
10 Correct 260 ms 9292 KB Output is correct
11 Correct 1 ms 336 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 492 ms 15948 KB Output is correct
13 Correct 708 ms 6216 KB Output is correct
14 Correct 157 ms 852 KB Output is correct
15 Correct 818 ms 8776 KB Output is correct
16 Correct 124 ms 18248 KB Output is correct
17 Correct 474 ms 11592 KB Output is correct
18 Correct 756 ms 18504 KB Output is correct
19 Correct 670 ms 18728 KB Output is correct
20 Correct 593 ms 17992 KB Output is correct
21 Correct 1 ms 336 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 504 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 508 KB Output is correct
12 Correct 308 ms 12616 KB Output is correct
13 Correct 214 ms 12872 KB Output is correct
14 Correct 271 ms 9800 KB Output is correct
15 Correct 300 ms 9544 KB Output is correct
16 Correct 213 ms 6796 KB Output is correct
17 Correct 306 ms 9772 KB Output is correct
18 Correct 268 ms 9288 KB Output is correct
19 Correct 486 ms 15948 KB Output is correct
20 Correct 702 ms 6216 KB Output is correct
21 Correct 168 ms 1096 KB Output is correct
22 Correct 825 ms 8824 KB Output is correct
23 Correct 123 ms 18248 KB Output is correct
24 Correct 499 ms 11592 KB Output is correct
25 Correct 755 ms 18504 KB Output is correct
26 Correct 661 ms 18760 KB Output is correct
27 Correct 604 ms 17992 KB Output is correct
28 Correct 633 ms 256000 KB Output is correct
29 Runtime error 1121 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 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 305 ms 12616 KB Output is correct
13 Correct 214 ms 12884 KB Output is correct
14 Correct 277 ms 9800 KB Output is correct
15 Correct 300 ms 9508 KB Output is correct
16 Correct 213 ms 6808 KB Output is correct
17 Correct 287 ms 9800 KB Output is correct
18 Correct 256 ms 9292 KB Output is correct
19 Correct 484 ms 15944 KB Output is correct
20 Correct 721 ms 6248 KB Output is correct
21 Correct 163 ms 1096 KB Output is correct
22 Correct 821 ms 8776 KB Output is correct
23 Correct 126 ms 18252 KB Output is correct
24 Correct 495 ms 11600 KB Output is correct
25 Correct 782 ms 18464 KB Output is correct
26 Correct 662 ms 18808 KB Output is correct
27 Correct 590 ms 17992 KB Output is correct
28 Correct 626 ms 256000 KB Output is correct
29 Runtime error 1100 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -