제출 #553921

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
553921		elazarkoren	게임 (IOI13_game)	C++17	80 / 100	3225 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;

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 n, m;

struct Seg1 {
    vector<ll> seg;
    vi lp, rp;
    Seg1() {
        Add();
    }
    inline void Add() {
        seg.push_back(0);
        lp.push_back(0);
        rp.push_back(0);
    }
    void update(int i, ll x, int ind, int l, int r) {
        if (l + 1 == r) {
            seg[ind] = x;
            return;
        }
        if (i < (l + r) >> 1) {
            if (!lp[ind]) {
                lp[ind] = seg.size();
                Add();
            }
            update(i, x, lp[ind], l, (l + r) >> 1);
        } else {
            if (!rp[ind]) {
                rp[ind] = seg.size();
                Add();
            }
            update(i, x, rp[ind], (l + r) >> 1, r);
        }
        seg[ind] = gcd2(lp[ind] ? seg[lp[ind]] : 0, rp[ind] ? seg[rp[ind]] : 0);
    }
    inline void update(int i, ll x) {
        update(i, x, 0, 0, m);
    }
    ll query(int a, int b, int ind, int l, int r) {
        if (a <= l && r <= b) return seg[ind];
        if (r <= a || b <= l) return 0;
        return gcd2(lp[ind] ? query(a, b, lp[ind], l, (l + r) >> 1) : 0,
                    rp[ind] ? query(a, b, rp[ind], (l + r) >> 1, r) : 0);
    }
    inline ll query(int a, int b) {
        return query(a, b, 0, 0, m);
    }
};


struct Seg2 {
    vector<Seg1> seg;
    vi lp, rp;
    Seg2() {
        Add();
    }
    inline void Add() {
        seg.push_back(Seg1());
        lp.push_back(0);
        rp.push_back(0);
    }
    void update(int i, int j, ll x, int ind, int l, int r) {
        if (l + 1 == r) {
            seg[ind].update(j, x);
            return;
        }
        if (i < (l + r) >> 1) {
            if (!lp[ind]) {
                lp[ind] = seg.size();
                Add();
            }
            update(i, j, x, lp[ind], l, (l + r) >> 1);
        } else {
            if (!rp[ind]) {
                rp[ind] = seg.size();
                Add();
            }
            update(i, j, x, rp[ind], (l + r) >> 1, r);
        }
        x = gcd2(lp[ind] ? seg[lp[ind]].query(j, j + 1) : 0, rp[ind] ? seg[rp[ind]].query(j, j + 1) : 0);
        seg[ind].update(j, x);
    }
    inline void update(int i, int j, ll x) {
        update(i, j, x, 0, 0, n);
    }
    ll query(int x1, int y1, int x2, int y2, int ind, int l, int r) {
        if (x1 <= l && r <= x2) return seg[ind].query(y1, y2);
        if (r <= x1 || x2 <= l) return 0;
        return gcd2(lp[ind] ? query(x1, y1, x2, y2, lp[ind], l, (l + r) >> 1) : 0,
                    rp[ind] ? query(x1, y1, x2, y2, rp[ind], (l + r) >> 1, r) : 0);
    }
    inline ll query(int x1, int y1, int x2, int y2) {
        return query(x1, y1, x2, y2, 0, 0, n);
    }
};


Seg2 mat;

void init(int R, int C) {
    n = R, m = C;
    mat = Seg2();
}

void update(int p, int q, long long k) {
    mat.update(p, q, k);
}

long long calculate(int p, int q, int u, int v) {
    return mat.query(p, q, u + 1, v + 1);
}

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