oj.uz

Submission #477620

# Submission time Handle Problem Language Result Execution time Memory
477620 2021-10-02T21:12:11 Z andrey27_sm Game (IOI13_game) C++17
0 / 100
 1 ms 424 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll c, r;
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 == NULL) 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 == NULL) v->lS = new Node();
            update(v->lS,l,m,t,val);
        }else{
            if (v->rS == NULL) v->rS = new Node();
            update(v->rS,m+1,r,t,val);
        }
        v->val = gcd(get_val(v->lS), get_val(v->rS));
        return;
    }
    ll get(Node *v,ll l,ll r,ll tl,ll tr){
        if(v == NULL 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,r,t,val);
    }
    ll get(ll tl,ll tr){
        return get(&root,0,r,tl,tr);
    }
    NodeST(){
        root = *new Node();
    }
};
struct Node2{
    Node2 *lS;
    Node2 *rS;
    NodeST val;
    Node2(){
        lS = NULL;
        rS = NULL;
        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 == NULL) v->lS = new Node2();
        update(v->lS,l,m,x,y,val);
    }else{
        if (v->rS == NULL) v->rS = new Node2();
        update(v->rS,m+1,r,x,y,val);
    }
    (v->val).update(y,val);
    return;
}
ll get(Node2 *v,ll l,ll r,ll xl,ll xr,ll yl,ll yr){
    if(v == NULL 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;
    ll ans = get(v->lS,l,m,xl,xr,yl,yr);
    ans += get(v->rS,m+1,r,xl,xr,yl,yr);
    return ans;
}
Node2 root;
void updates(ll x,ll y,ll val){
    update(&root,0,c,x,y,val);
}
ll get(ll xl,ll xr,ll yl,ll yr){
    return get(&root,0,c,xl,xr,yl,yr);
}
/*int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> R >> C >> n;
    for (int i = 0; i < n; ++i) {
        int type  = 0;
        cin >> type;
        if(type == 1){
            cin >> x >> y >> t;
            update(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){
    r = 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 208 KB Output is correct
2 Incorrect 1 ms 424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 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 208 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 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 0 ms 208 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -