oj.uz

Submission #477694

# Submission time Handle Problem Language Result Execution time Memory
477694 2021-10-03T06:21:24 Z andrey27_sm Game (IOI13_game) C++17
0 / 100
 1 ms 336 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll 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 and y == 0) return 0;
    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,ll l,ll r,ll 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,ll l,ll r,ll tl,ll 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,ll l,ll r,ll x,ll 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,ll l,ll r,ll xl,ll xr,ll yl,ll 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(ll x,ll y,ll val){
    update(&root,0,rl,x,y,val);
}
ll get(ll xl,ll xr,ll yl,ll yr){
    return get(&root,0,rl,xl,xr,yl,yr);
}

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,Q,U,V);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -