제출 #895640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
895640		vjudge1	Game (IOI13_game)	C++17	37 / 100	955 ms	256000 KiB

game

#include <bits/stdc++.h>
using namespace std;

#include "game.h"
long long gcd2(long long x, long long y) { return __gcd(x, y); }

struct SegmentTree {
    int n, m;
    vector<vector<long long>> gcd;

    SegmentTree() {}
    SegmentTree(int n, int m) : n(n), m(m), gcd(4 * n, vector<long long>(4 * m, 0)) {}

    int i, j, supidx;
    long long val;
    bool is_leaf;
    int i0, j0, i1, j1;

    void subchange(int idx, int l, int r) {
        if (l + 1 == r) {
            if (is_leaf) gcd[supidx][idx] = val;
            else gcd[supidx][idx] = gcd2(gcd[2 * supidx + 1][idx], gcd[2 * supidx + 2][idx]);
        } else {
            int m = (l + r) >> 1;
            if (j < m) subchange(2 * idx + 1, l, m);
            else subchange(2 * idx + 2, m, r);
            if (is_leaf) gcd[supidx][idx] = gcd2(gcd[supidx][2 * idx + 1], gcd[supidx][2 * idx + 2]);
            else gcd[supidx][idx] = gcd2(gcd[2 * supidx + 1][idx], gcd[2 * supidx + 2][idx]);
        }
    }
    void supchange(int idx, int l, int r) {
        if (l + 1 == r) {
            supidx = idx;
            is_leaf = true;
            subchange(0, 0, m);
        } else {
            int m = (l + r) >> 1;
            if (i < m) supchange(2 * idx + 1, l, m);
            else supchange(2 * idx + 2, m, r);
            supidx = idx;
            is_leaf = false;
            subchange(0, 0, this->m);
        }
    }
    void change(int i, int j, long long val) {
        this->i = i;
        this->j = j;
        this->val = val;
        supchange(0, 0, n);
    }

    long long subGetGcd(int idx, int l, int r) {
        if (r <= j0 || j1 <= l) return 0LL;
        if (j0 <= l && r <= j1) return gcd[supidx][idx];
        int m = (l + r) >> 1;
        return gcd2(subGetGcd(2 * idx + 1, l, m), subGetGcd(2 * idx + 2, m, r));
    }
    long long supGetGcd(int idx, int l, int r) {
        if (r <= i0 || i1 <= l) return 0LL;
        if (i0 <= l && r <= i1) { supidx = idx; return subGetGcd(0, 0, m); }
        int m = (l + r) >> 1;
        return gcd2(supGetGcd(2 * idx + 1, l, m), supGetGcd(2 * idx + 2, m, r));
    }
    long long getGcd(int i0, int j0, int i1, int j1) {
        this->i0 = i0;
        this->j0 = j0;
        this->i1 = i1;
        this->j1 = j1;
        return supGetGcd(0, 0, n);
    }
};

SegmentTree seg;

void init(int n, int m) {
    seg = SegmentTree(n, m);
}

void update(int i, int j, long long val) {
    seg.change(i, j, val);
}

long long calculate(int i0, int j0, int i1, int j1) {
    i1++;
    j1++;
    return seg.getGcd(i0, j0, i1, j1);
}

//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    int n, m, q;
//    cin >> n >> m >> q;
//    init(n, m);
//    for (int i = 0; i < q; i++) {
//        int type;
//        cin >> type;
//        if (type == 1) {
//            int i, j;
//            long long val;
//            cin >> i >> j >> val;
//            update(i, j, val);
//        }
//        if (type == 2) {
//            int i0, j0, i1, j1;
//            cin >> i0 >> j0 >> i1 >> j1;
//            cout << calculate(i0, j0, i1, j1) << '\n';
//        }
//    }
//}

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