Submission #1087630

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087630		Zero_OP	Game (IOI13_game)	C++14	63 / 100	1097 ms	256000 KiB

game

#ifndef LOCAL
#include "game.h"
#endif //LOCAL

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;


long long gcd2(long long X, long long Y) {
//    cout << X << ' ' << Y << '\n';
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int N, M;

struct node1D{
    node1D *left, *right;
    long long g;

    node1D(ll g = 0) : g(g), left(nullptr), right(nullptr) {}
    node1D(node1D* left, node1D *right) : left(left), right(right), g(gcd2(left -> g, right -> g)) {}
};

void define1D(node1D*& cur){
    if(cur == nullptr) cur = new node1D();
}

ll eval(node1D* cur){
    if(cur == nullptr) return 0;
    return cur -> g;
}

struct node2D{
    node2D *left, *right;
    node1D *tree;

    node2D() : left(nullptr), right(nullptr), tree(nullptr) {}
    node2D(node2D* left, node2D* right) : left(left), right(right), tree(nullptr) {}
} *tree2D;

void define2D(node2D*& cur){
    if(cur == nullptr) cur = new node2D();
}

void update_y(int lx, int rx, node1D* tl, node1D* tr, node1D*& idy, int ly, int ry, int y, long long k){
    define1D(idy);

    if(ly == ry){
        if(lx == rx) (idy -> g) = k;
        else (idy -> g) = gcd2(eval(tl), eval(tr));
    } else{
        int mid = (ly + ry) >> 1;
        if(y <= mid) update_y(lx, rx, (tl == nullptr ? nullptr : tl -> left), (tr == nullptr ? nullptr : tr -> left), idy -> left, ly, mid, y, k);
        else update_y(lx, rx, (tl == nullptr ? nullptr : tl -> right), (tr == nullptr ? nullptr : tr -> right), idy -> right, mid + 1, ry, y, k);

        (idy -> g) = gcd2(eval(idy -> left), eval(idy -> right));
    }
}

void update_x(node2D* &idx, int lx, int rx, int x, int y, long long k){
    define2D(idx);

    if(lx < rx){
        int mid = lx + rx >> 1;
        if(x <= mid) update_x(idx -> left, lx, mid, x, y, k);
        else update_x(idx -> right, mid + 1, rx, x, y, k);
    }

    update_y(lx, rx, (idx -> left == nullptr ? nullptr : idx -> left -> tree),
              (idx -> right == nullptr ? nullptr : idx -> right -> tree), idx -> tree, 0, M - 1, y, k);
}

long long query_y(node1D* idy, int ly, int ry, int u, int v){
    if((u <= ly && ry <= v) || idy == nullptr) return eval(idy);
    int mid = ly + ry >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_y(idy -> left, ly, mid, u, v));
    if(mid < v) g = gcd2(g, query_y(idy -> right, mid + 1, ry, u, v));
    return g;
}

long long query_x(node2D* idx, int lx, int rx, int u, int v, int p, int q){
    if((u <= lx && rx <= v) || idx == nullptr) return query_y((idx == nullptr ? nullptr : idx -> tree), 0, M - 1, p, q);
    int mid = lx + rx >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_x(idx -> left, lx, mid, u, v, p, q));
    if(mid < v) g = gcd2(g, query_x(idx -> right, mid + 1, rx, u, v, p, q));
    return g;
}

void init(int R, int C) {
    N = R;
    M = C;
}

void update(int P, int Q, long long K) {
    update_x(tree2D, 0, N - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query_x(tree2D, 0, N - 1, P, U, Q, V);
}


#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int Q;
    cin >> N >> M >> Q;

    init(N, M);

    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y; long long z;
            cin >> x >> y >> z;
            update(x, y, z);
        } else{
            int p, q, u, v;
            cin >> p >> q >> u >> v;
//            cout << calculate(p, q, u, v) << '\n';
        }
    }


    return 0;
}
#endif // LOCAL

Compilation message (stderr)

game.cpp: In constructor 'node1D::node1D(ll)':
game.cpp:47:15: warning: 'node1D::g' will be initialized after [-Wreorder]
   47 |     long long g;
      |               ^
game.cpp:46:13: warning:   'node1D* node1D::left' [-Wreorder]
   46 |     node1D *left, *right;
      |             ^~~~
game.cpp:49:5: warning:   when initialized here [-Wreorder]
   49 |     node1D(ll g = 0) : g(g), left(nullptr), right(nullptr) {}
      |     ^~~~~~
game.cpp: In function 'void update_x(node2D*&, int, int, int, int, long long int)':
game.cpp:93:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
game.cpp: In function 'long long int query_y(node1D*, int, int, int, int)':
game.cpp:104:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid = ly + ry >> 1;
      |               ~~~^~~~
game.cpp: In function 'long long int query_x(node2D*, int, int, int, int, int, int)':
game.cpp:113:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  113 |     int mid = lx + rx >> 1;
      |               ~~~^~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20