oj.uz

답안 #117513

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
117513 2019-06-16T11:29:27 Z someone_aa 게임 (IOI13_game) C++17
0 / 100
 3 ms 640 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 xlb, int xrb, int ind, ll uval) {
        if(lb == rb) {
            if(xlb == xrb) val = uval;
            else val = gcd2(val, uval);
        }
        else {
            int mid = (lb + rb) / 2;

            if(ind <= mid) {
                if(leftchild == NULL) {
                    leftchild = new node_y(lb, mid);
                }
                leftchild -> update(xlb, xrb, ind, uval);
            }
            else {
                if(rightchild == NULL) {
                    rightchild = new node_y(mid+1, rb);
                }
                rightchild -> update(xlb, xrb, 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";
        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);
            }
        }

        root->update(lb, rb, 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:121:17: warning: unused variable 'mid' [-Wunused-variable]
             int mid = (lb + rb) / 2;
                 ^~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Incorrect 2 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Incorrect 2 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Incorrect 1 ms 256 KB Output isn't correct
5 Halted 0 ms 0 KB -