Submission #957440

#	Time	Username	Problem	Language	Result	Execution time	Memory
957440		bobbilyking	Game (IOI13_game)	C++17	0 / 100	1 ms	604 KiB

game

#include "game.h"

#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")

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

typedef long long int ll;
typedef long double ld;
typedef pair<ll, ll> pl;
typedef vector<ll> vl;
#define FD(i, r, l) for(ll i = r; i > (l); --i)

#define K first
#define V second
#define G(x) ll x; cin >> x;
#define GD(x) ld x; cin >> x;
#define GS(s) string s; cin >> s;
#define EX(x) { cout << x << '\n'; exit(0); }
#define A(a) (a).begin(), (a).end()
#define F(i, l, r) for (ll i = l; i < (r); ++i)

template<typename A, typename B>
A& chmax(A &a, B b) { return a < b ? (a=b): a; }

template<typename A, typename B>
A& chmin(A &a, B b) { return a > b ? (a=b): a; }


int MAXR, MAXC;

struct Seg1D {
    Seg1D* c[2]{};
    ll val = 0;

    void modify(int l, int r, int i, long long k) {
        if (l == r) {
            val = k; return;
        }
        int m = (l + r) / 2;
        if (i <= m) {
            if (!c[0]) c[0] = new Seg1D();
            c[0]->modify(l, m, i, k);
        } else {
            if (!c[1]) c[1] = new Seg1D();
            c[1]->modify(m+1, r, i, k); 
        }
        val = 0;
        F(i, 0, 2) if (c[i]) val = gcd(val, c[i]->val);
    }

    ll query(int l, int r, int qxl, int qxr) {
        ll res = 0;
        if (qxr < l || r < qxl) return 0;
        if (qxl <= l and r <= qxr) {
            return val;
        }
        int m = (l + r) / 2;
        if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr));
        if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr));
        return res;
    }
};

struct Seg2D { // outer layer of segtrees
    Seg2D* c[2]{};
    Seg1D* repr = nullptr;

    void modify(int l, int r, int x, int y, long long k) {
        // log(n) segtree representations 
        if (!repr) repr = new Seg1D();
        repr->modify(0, MAXC, y, k);
        if (l == r) {
            // cout << "NEW MODIFY AT " << l << " " << r << " : " << x << "  "<< y << " FOR " << k << endl;
            // cout << "YO.... " << repr->val << endl;
            // cout << "ADDRESS OF THIS NODE: " << this << endl;
            return;
        }
        int m = (l + r) / 2;
        if (x <= m) {
            if (!c[0]) c[0] = new Seg2D();
            c[0]->modify(l, m, x, y, k);
        } else {
            if (!c[1]) c[1] = new Seg2D();
            c[1]->modify(m+1, r, x, y, k); 
        }
    }

    ll query(int l, int r, int qxl, int qxr, pair<int, int> yrange) {
        if (qxr < l || r < qxl) return 0;
        // cout << "HAHA " << l << " " << r << " | " << qxl << " " << qxr << endl;
        if (qxl <= l and r <= qxr) {
            // cout << "HOW THE FUCK " << endl;
            // cout << "ADDRESS OF THIS NODE: " << this << endl;
            // cout << l << " " << r << " INCLUDED " << endl;
            if (!repr) return 0;
            // cout << "PULL FROM REPR " << endl;
            return repr->query(0, MAXC, yrange.K, yrange.V);
        }
        ll res = 0;

        int m = (l + r) / 2;

        // cout << "AT " << l << " " << r << " SHOULD DEF HAVE " << c[0] << endl;
        if (c[0]) res = gcd(res, c[0]->query(l, m, qxl, qxr, yrange));
        if (c[1]) res = gcd(res, c[1]->query(m + 1, r, qxl, qxr, yrange));

        // cout << "WAT " << res << endl;
        return res;
    }
} root;

void init(int R, int C) {
    MAXR = R-1, MAXC = C-1;
}

void update(int P, int Q, long long k) {
    root.modify(0, MAXR, P, Q, k);
}

long long calculate(int p, int q, int u, int v) {
    /* ... */
    assert(p <= u and u <= MAXR);
    assert(q <= v and v <= MAXC);
    return root.query(0, MAXR, p, u, make_pair(q, v));
}

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