oj.uz

Submission #916420

# Submission time Handle Problem Language Result Execution time Memory
916420 2024-01-25T20:19:49 Z AverageAmogusEnjoyer Game (IOI13_game) C++17
0 / 100
 1 ms 532 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
const int nax = 1e9;
struct node_st2 {
    ll ans=0;
    node_st2 *left_child=nullptr,*right_child=nullptr;
    int l,r;
    node_st2(int _l,int _r) : l(_l) , r(_r) {}  
    void extend() {
        if (!left_child && l != r) {
            int mid = (l+r)/2;
            left_child = new node_st2(l,mid);
            right_child = new node_st2(mid+1,r);
        }
    }
    void upd(int p,ll x) {
        extend();
        ans=gcd(ans,x);
        if (left_child) {
            if (p <= left_child->r) {
                left_child->upd(p,x);
            } else {
                right_child->upd(p,x);
            }
        }
    }
    ll get_gcd(int tl,int tr) {
        if (tl <= l && r <= tr) {
            return ans;
        }
        if (tr < l || tl > r) {
            return 0LL;
        }
        extend();
        return gcd(left_child->get_gcd(tl,tr),right_child->get_gcd(tl,tr));
    }
};
struct node_st1 { 
    node_st2 *root;
    node_st1 *left_child=nullptr,*right_child=nullptr;
    int l,r;
    node_st1(int _l,int _r) {
        l = _l;
        r = _r;
        root = new node_st2(0,nax);
    }
    void extend() {
        if (!left_child && l != r) {
            int mid = (l+r)/2;
            left_child = new node_st1(l,mid);
            right_child = new node_st1(mid+1,r);
        }
    }
    void upd(int x,int y,ll nw) {
        extend();
        root->upd(y,nw);
        if (left_child) {
            if (x <= left_child->r) {
                left_child->upd(x,y,nw);
            } else {
                right_child->upd(x,y,nw);
            }
        }
    }
    ll get_gcd(int x1,int y1,int x2,int y2) {
        if (x1 <= l && r <= x2) {
            return root->get_gcd(y1,y2);
        }
        if (x2 < l || x1 > r) { 
            return 0LL;
        }
        extend();
        return gcd(left_child->get_gcd(x1,y1,x2,y2),right_child->get_gcd(x1,y1,x2,y2));
    }
};
node_st1 *root = new node_st1(0,nax);
void init(int r,int c) {
    // AMOGUS
}
void update(int x,int y,ll nw) {
    root->upd(x,y,nw);
}
ll calculate(int x1,int y1,int x2,int y2) {
    return root->get_gcd(x1,y1,x2,y2);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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