oj.uz

답안 #373730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
373730 2021-03-05T14:30:21 Z cheissmart 게임 (IOI13_game) C++14
0 / 100
 1 ms 364 KB 
#include "game.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define V vector
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << "LINE(" << __LINE__ << ") -> " << #x << " is " << (x) << endl
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
 
const int INF = 1e9 + 7;

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;
}

int R, C;

struct seg_y {
    struct node {
        node *l, *r;
        ll g; // gcd
        node(int _g = 0) {
            l = r = nullptr;
            g = _g;
        }
    };
    node* root;
    seg_y() {
        root = nullptr;
    }
    ll g(node* t) {
        return t ? t -> g : 0LL;
    }
    void pull(node* t) {   
        t -> g = gcd2(g(t -> l), g(t -> r));
    }
    void upd(node* &t, int y, ll val, int tl = 0, int tr = C) {
        if(!t) t = new node();
        if(tr - tl == 1) {
            t -> g = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if(y < tm) upd(t -> l, y, val, tl, tm);
        else upd(t -> r, y, val, tm, tr);
        pull(t);
    }
    ll qry(node* t, int l, int r, int tl = 0, int tr = C) {
        if(!t) return 0;
        if(l <= tl && tr <= r) return t -> g;
        int tm = (tl + tr) / 2;
        ll g = 0;
        if(l < tm) g = gcd2(g, qry(t -> l, l, r, tl, tm));
        if(r > tm) g = gcd2(g, qry(t -> r, l, r, tm, tr));
        return g;
    }
    void upd(int y, int val) {
        upd(root, y, val);
    }
    ll qry(int l, int r) {
        return qry(root, l, r);
    }
    ll qry(int y) {
        return qry(y, y + 1);
    }
};

struct seg_x {
    struct node {
        node *l, *r;
        seg_y seg;
        node() {
            l = r = nullptr;
        }
    };
    node* root;
    void pull(node* t, int y) {
        ll g = 0;
        if(t -> l) g = gcd2(g, t -> l -> seg.qry(y));
        if(t -> r) g = gcd2(g, t -> r -> seg.qry(y));
        t -> seg.upd(y, g);
    }
    void upd(node* &t, int x, int y, ll val, int tl = 0, int tr = R) {
        if(!t) t = new node();
        if(tr - tl == 1) {
            t -> seg.upd(y, val);
            return;
        }
        int tm = (tl + tr) / 2;
        if(x < tm) upd(t -> l, x, y, val, tl, tm);
        else upd(t -> r, x, y, val, tm, tr);
        pull(t, y);
    }
    void upd(int x, int y, ll val) {
        upd(root, x, y, val);
    }
    ll qry(node* t, int xl, int xr, int yl, int yr, int tl = 0, int tr = R) {
        if(!t) return 0;
        if(xl <= tl && tr <= xr) return t -> seg.qry(yl, yr);
        int tm = (tl + tr) / 2;
        ll g = 0;
        if(xl < tm) g = gcd2(g, qry(t -> l, xl, xr, yl, yr, tl, tm));
        if(xr > tm) g = gcd2(g, qry(t -> r, xl, xr, yl, yr, tm, tr));
        return g;
    }
    ll qry(int xl, int xr, int yl, int yr) {
        return qry(root, xl, xr, yl, yr);
    }
} seg;

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

void update(int P, int Q, long long K) {
    seg.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return seg.qry(P, U + 1, Q, V + 1);
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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