Submission #117511

# Submission time Handle Problem Language Result Execution time Memory
117511 2019-06-16T11:19:29 Z someone_aa Game (IOI13_game) C++17
0 / 100
2 ms 384 KB
#include "game.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
int r, c;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

class node_y {
public:
    ll val;
    int lb, rb;

    node_y *leftchild, *rightchild;

    node_y(int _lb, int _rb) {
        lb = _lb; rb = _rb;
        leftchild = rightchild = NULL;
        val = 0LL;
    }
    ll get_val(node_y *x) {
        if(x == NULL) return 0LL;
        else return x->val;
    }
    void update(int ind, ll uval) {
        if(lb == rb) {
            val = gcd2(val, uval);
        }
        else {
            int mid = (lb + rb) / 2;

            if(ind <= mid) {
                if(leftchild == NULL) {
                    leftchild = new node_y(lb, mid);
                }
                leftchild -> update(ind, uval);
            }
            else {
                if(rightchild == NULL) {
                    rightchild = new node_y(mid+1, rb);
                }
                rightchild -> update(ind, uval);
            }

            val = gcd2(get_val(leftchild), get_val(rightchild));
        }
        //cout<<"Done "<<lb<<" "<<rb<<" -> "<<val<<"\n";
    }
    ll query(int ql, int qr) {
        if(lb > qr || rb < ql) return 0LL;
        else if(lb >= ql && rb <= qr) {
            //cout<<"Enter: "<<lb<<", "<<rb<<" - "<<val<<"\n";
            return val;
        }
        else {
            ll a, b;
            if(leftchild == NULL) a = 0LL;
            else a = leftchild->query(ql, qr);

            if(rightchild == NULL) b = 0LL;
            else b = rightchild->query(ql, qr);

            return gcd2(a, b);
        }
    }
};

class node_x {
public:
    node_y *root;
    node_x *leftchild, *rightchild;
    int lb, rb;

    node_x(int _lb, int _rb, int _lby, int _rby) {
        lb = _lb; rb = _rb;
        leftchild = rightchild = NULL;
        root = new node_y(_lby, _rby);
    }
    void update(int x, int y, ll val) {
        //cout<<"At x: "<<lb<<", "<<rb<<"\n";
        root->update(y, val);
        if(lb != rb) {
            int mid = (lb + rb) / 2;

            if(x <= mid) {
                if(leftchild == NULL) {
                    leftchild = new node_x(lb, mid, 0, c-1);
                }
                leftchild -> update(x, y, val);
            }
            else {
                if(rightchild == NULL) {
                    rightchild = new node_x(mid+1, rb, 0, c-1);
                }
                rightchild -> update(x, y, val);
            }
        }
    }
    ll query(int qlx, int qrx, int qly, int qry) {
        if(lb > qrx || rb < qlx) {
            return 0LL;
        }
        else if(lb >= qlx && rb <= qrx) {
            //<<lb<<", "<<rb<<"\n";
            ll x = root -> query(qly, qry);
            return x;
        }
        else {
            int mid = (lb + rb) / 2;

            ll a, b;
            if(leftchild == NULL) a = 0LL;
            else a = leftchild->query(qlx, qrx, qly, qry);

            if(rightchild == NULL) b = 0LL;
            else b = rightchild -> query(qlx, qrx, qly, qry);

            return gcd2(a, b);
        }
    }
};

node_x *root;

void init(int R, int C) {
    r = R; c = C;

    /*cout<<"Init: "<<gcd2(3696878681496, 20551290769769760)<<"\n";

    vector<ll> v = {20551290769769760, 23127673031438976, 287635645813796280};
    ll x = 0LL;
    for(ll i:v) {
        x = gcd2(i, x);
    }
    cout<<x<<"\n";*/
    root = new node_x(0, r-1, 0, c-1);
}

void update(int P, int Q, long long K) {
    //cout<<"Inserting "<<K<<" at ("<<P<<", "<<Q<<")\n";
    root->update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return root->query(P, U, Q, V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In member function 'long long int node_x::query(int, int, int, int)':
game.cpp:119:17: warning: unused variable 'mid' [-Wunused-variable]
             int mid = (lb + rb) / 2;
                 ^~~
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -