Submission #426616

#	Time	Username	Problem	Language	Result	Execution time	Memory
426616		Aldas25	Game (IOI13_game)	C++14	37 / 100	13071 ms	14988 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;

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

struct segtree1 {
    struct node1 {
        ll fr, to;
        ll val;
        node1 * leCh;
        node1 * riCh;

        node1 (ll _fr, ll _to) {
            fr = _fr;
            to = _to;
            val = 0;
            leCh = riCh = nullptr;
        }

        void upd () {
            ll mid = (fr+to)/2;
            if (!leCh)
                leCh = new node1 (fr, mid);
            if (!riCh)
                riCh = new node1 (mid+1, to);
        }
    };

    void upd (ll p, ll newVal, node1 * cur) {
        if (cur->fr == cur->to){
            cur->val = newVal;
            return;
        }
        ll mid = (cur->fr) + (cur->to);
        mid /= 2;
        cur->upd();
        if (p <= mid)
            upd(p, newVal, cur->leCh);
        else
            upd (p, newVal, cur->riCh);

        cur->val = gcd2(cur->leCh->val, cur->riCh->val);
    }

    ll get(ll rfr, ll rto, node1 * cur) {
        if (rfr > (cur->to) || rto < (cur->fr)) return 0;
        if (rfr <= (cur->fr) && (cur->to) <= rto) return cur->val;
        if (!(cur->leCh)) return 0;
        cur->upd();
        return gcd2(get(rfr, rto, cur->leCh), get(rfr, rto, cur->riCh));
    }

    node1 * root = new node1 (0, 1e9);

    void upd (ll pos, ll newVal) {
        upd(pos, newVal, root);
    }

    ll get (ll fr, ll to) {
        return get(fr, to, root);
    }

};

segtree1 tree[2100];

void init(int R, int C) {

}

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

long long calculate(int P, int Q, int U, int V) {
    ll ans = 0;
    FOR(i, P, U) {
        //cout << "  i = " << i << " q=" << Q << " v=" << V << " get= " << tree[i].get(Q,V) << endl;
        ans = gcd2(ans, tree[i].get(Q, V));
    }
    return ans;
}

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