Submission #426813

#	Time	Username	Problem	Language	Result	Execution time	Memory
426813		Aldas25	Game (IOI13_game)	C++14	63 / 100	3793 ms	256004 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);
    }

};

struct segtree2 {
    struct node2 {
        ll fr, to;
        segtree1 * tr;
        node2 * leCh;
        node2 * riCh;

        node2 (ll _fr, ll _to) {
            fr = _fr;
            to = _to;
            tr = new segtree1();
            leCh = riCh = nullptr;
        }

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

    ll get(ll frx, ll tox, ll fry, ll toy, node2 * cur) {
        if (frx > (cur->to) || tox < (cur->fr)) {
          //  cout << " in get, discard frx = " << frx << " tox = " << tox << "fry = " << fry
          //<< " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
            return 0;
        }
        if (frx <= (cur->fr) && (cur->to) <= tox) {
            ll ret = cur->tr->get(fry, toy);
        //    cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
         // << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
           // cout << "    returnin ret = " << ret << endl;
            return ret;
        }
        if (!(cur->leCh)) return 0;
        //cur->upd();
        ll ret = gcd2(get(frx, tox, fry, toy, cur->leCh), get(frx, tox, fry, toy, cur->riCh));
       // cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
        //  << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
        //cout << "     returning ret = " << ret << endl;
        return ret;
    }

    void upd (ll px, ll py, ll newVal, node2 * cur) {
        if (cur->fr == cur->to){
           // cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " newVal = " << newVal << endl;
            cur->tr->upd(py, newVal);
            return;
        }
        ll mid = (cur->fr) + (cur->to);
        mid /= 2;
        cur->upd();
        if (px <= mid)
            upd(px, py, newVal, cur->leCh);
        else
            upd (px, py, newVal, cur->riCh);

       // cur->val = gcd2(cur->leCh->val, cur->riCh->val);
        ll g = gcd2(get(cur->fr, mid, py, py, cur->leCh), get(mid+1, cur->to, py, py, cur->riCh));
        cur->tr->upd (py, g);
//        cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " g = " << g << endl;
    }

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

    void upd (ll posx, ll posy, ll newVal) {
        upd(posx, posy, newVal, root);
    }

    ll get (ll frx, ll fry, ll tox, ll toy) {
        return get(frx, fry, tox, toy, root);
    }
};

segtree2 tree;

void init(int R, int C) {

}

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

long long calculate(int P, int Q, int U, int V) {
    //cout << "------------------doing get" << endl;
    ll ans = tree.get(P, U, Q, V);
    //cout << "---------------------after get" << endl;
    return ans;
}

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