Submission #1090302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090302		vjudge1	Game (IOI13_game)	C++17	37 / 100	13067 ms	37280 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct SegTree {
    int n;
    vector<ll> tree;

    void init(int _n) { n = _n; tree.resize(4*_n); }

    void update(int u, int tl, int tr, int p, ll v) {
        if(tl == tr) {
            tree[u] = v;
        } else {
            int tm = (tl + tr) / 2;
            if(p <= tm) update(2*u, tl, tm, p, v);
            else update(2*u+1, tm+1, tr, p, v);
            tree[u] = gcd(tree[2*u], tree[2*u+1]);
        }
    }

    ll query(int u, int tl, int tr, int l, int r) {
        if(l > tr || tl > r || !tree[u]) return 0;
        if(l <= tl && tr <= r) return tree[u];
        int tm = (tl + tr) / 2;
        return gcd(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void update(int p, ll v) { update(1, 0, n-1, p, v); }
    ll query(int l, int r) { return query(1, 0, n-1, l, r); }
};

vector<SegTree> tree;

void init(int R, int C) {
    tree.resize(R);
    for(int i=0; i<R; i++) tree[i].init(C);
}

void update(int P, int Q, ll K) {
    tree[P].update(Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    ll ans = 0;
    for(int i=P; i<=U; i++) ans = gcd(ans, tree[i].query(Q, V));
    return ans;
}

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