oj.uz

Submission #477754

# Submission time Handle Problem Language Result Execution time Memory
477754 2021-10-03T11:35:15 Z andrey27_sm Game (IOI13_game) C++17
63 / 100
 1521 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int c, rl;
struct Node{
    Node* lS;
    Node* rS;
    ll val;
    Node(){
        val = 0;
        lS = nullptr;
        rS = nullptr;
    }
};
ll gcd(ll x,ll y){
    if(x == 0 or y == 0) return max(x,y);
    return __gcd(x,y);
}
ll get_val(Node *v){
    if(v == nullptr) return 0;
    return v->val;
}
struct NodeST{
    Node root;
    void update(Node* v,int l,int r,int t,ll val){
        if (l == r){
            (v->val) = val;
            return;
        }
        ll m = (l+r)/2;
        if (t <= m){
            if (v->lS == nullptr) v->lS = new Node();
            update(v->lS,l,m,t,val);
        }else{
            if (v->rS == nullptr) v->rS = new Node();
            update(v->rS,m+1,r,t,val);
        }
        v->val = gcd(get_val(v->lS),get_val(v->rS));
    }
    ll get(Node *v,int l,int r,int tl,int tr){
        if(v == nullptr or r < tl or tr < l) return 0;
        if(tl <= l and r <= tr) {
            return v->val;
        }
        ll m = (l+r)/2;
        return gcd(get(v->rS,m+1,r,tl,tr),get(v->lS,l,m,tl,tr));
    }
    void update(ll t,ll val){
        return update(&root,0,c,t,val);
    }
    ll get(ll tl,ll tr){
        return get(&root,0,c,tl,tr);
    }
    NodeST(){
        root = *new Node();
    }
};
struct Node2{
    Node2 *lS;
    Node2 *rS;
    NodeST val;
    Node2(){
        lS = nullptr;
        rS = nullptr;
        val = *new NodeST();
    }
};
void update(Node2* v,int l,int r,int x,int y,ll val){
    if (l == r){
        (v->val).update(y,val);
        return;
    }
    ll m = (l+r)/2;
    if (x <= m){
        if (v->lS == nullptr) v->lS = new Node2();
        update(v->lS,l,m,x,y,val);
    }else{
        if (v->rS == nullptr) v->rS = new Node2();
        update(v->rS,m+1,r,x,y,val);
    }
    ll new_val = 0;
    if(v->lS) new_val=gcd(new_val,(v->lS)->val.get(y,y));
    if(v->rS) new_val=gcd(new_val,(v->rS)->val.get(y,y));
    v->val.update(y,new_val);
}
ll get(Node2 *v,int l,int r,int xl,int xr,int yl,int yr){
    if(v == nullptr or r < xl or xr < l) return 0;
    if(xl <= l and r <= xr) {
        return (v->val).get(yl,yr);
    }
    ll m = (l+r)/2;
    return gcd(get(v->lS,l,m,xl,xr,yl,yr),get(v->rS,m+1,r,xl,xr,yl,yr));
}
Node2 root;
void updates(int x,int y,ll val){
    update(&root,0,rl,x,y,val);
}
ll get(int xl,int xr,int yl,int yr){
    return get(&root,0,rl,xl,xr,yl,yr);
}



/*
int main() {
    int R,C,n;
    cin >> R >> C >> n;
    rl = R+1;
    c = C+1;
    for (int i = 0; i < n; ++i) {
        int type  = 0;
        cin >> type;
        if(type == 1){
            int x,y,t;
            cin >> x >> y >> t;
            updates(x,y,t);
        }
        else{
            int x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << get(x1,x2,y1,y2) << "\n";
        }
    }
    return 0;
}
*/
void init(int R,int C){
    rl = R+1;
    c = C+1;
    root = *new Node2();
}
void update(int P,int Q,ll K){
    updates(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
    return get(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 236 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 537 ms 13044 KB Output is correct
5 Correct 376 ms 13252 KB Output is correct
6 Correct 473 ms 10432 KB Output is correct
7 Correct 521 ms 10184 KB Output is correct
8 Correct 359 ms 7124 KB Output is correct
9 Correct 507 ms 10448 KB Output is correct
10 Correct 453 ms 9892 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 783 ms 15916 KB Output is correct
13 Correct 1291 ms 6344 KB Output is correct
14 Correct 284 ms 908 KB Output is correct
15 Correct 1521 ms 9120 KB Output is correct
16 Correct 494 ms 18496 KB Output is correct
17 Correct 749 ms 11716 KB Output is correct
18 Correct 1282 ms 18736 KB Output is correct
19 Correct 1101 ms 18936 KB Output is correct
20 Correct 1016 ms 18320 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 491 ms 12992 KB Output is correct
13 Correct 364 ms 13252 KB Output is correct
14 Correct 468 ms 10508 KB Output is correct
15 Correct 496 ms 10184 KB Output is correct
16 Correct 342 ms 7068 KB Output is correct
17 Correct 499 ms 10392 KB Output is correct
18 Correct 469 ms 9880 KB Output is correct
19 Correct 771 ms 15940 KB Output is correct
20 Correct 1273 ms 6244 KB Output is correct
21 Correct 282 ms 940 KB Output is correct
22 Correct 1505 ms 8968 KB Output is correct
23 Correct 489 ms 18500 KB Output is correct
24 Correct 767 ms 11752 KB Output is correct
25 Correct 1335 ms 18816 KB Output is correct
26 Correct 1085 ms 19012 KB Output is correct
27 Correct 1024 ms 18372 KB Output is correct
28 Runtime error 940 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 477 ms 13024 KB Output is correct
13 Correct 370 ms 13236 KB Output is correct
14 Correct 472 ms 10404 KB Output is correct
15 Correct 527 ms 10160 KB Output is correct
16 Correct 348 ms 6952 KB Output is correct
17 Correct 514 ms 10308 KB Output is correct
18 Correct 462 ms 9848 KB Output is correct
19 Correct 840 ms 15968 KB Output is correct
20 Correct 1287 ms 6360 KB Output is correct
21 Correct 296 ms 964 KB Output is correct
22 Correct 1518 ms 9024 KB Output is correct
23 Correct 496 ms 18424 KB Output is correct
24 Correct 743 ms 11664 KB Output is correct
25 Correct 1288 ms 18820 KB Output is correct
26 Correct 1087 ms 19144 KB Output is correct
27 Correct 1035 ms 18392 KB Output is correct
28 Runtime error 912 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -