Submission #925221

#	Time	Username	Problem	Language	Result	Execution time	Memory
925221		Nxmkxing	Game (IOI13_game)	C++14	0 / 100	1 ms	600 KiB

game

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

typedef long long ll;

typedef pair<int, int> pii;

ll gcd2(ll a, ll b) {
    if (b == 0) return a;
    return gcd2(b, a % b);
}

struct Treap {
  private:
    struct Node {
        pii key;
        int prior;
        ll val, gcd;
        Node *l, *r;
    
        Node(pii key, int val) : key(key), prior(rand()), val(val), gcd(val), l(nullptr), r(nullptr) {}
    };
  private:
    typedef struct Node* pnode;
  private:
    pnode root;

    void clear(pnode t) {
        if (t) {
            clear(t->l);
            clear(t->r);
            delete t;
        }
    }

    ll gcd(pnode t) {
        return t ? t->gcd : 0;
    }

    void upd(pnode t) {
        if (t) {
            t->gcd = gcd2(gcd(t->l), gcd(t->r));
            t->gcd = gcd2(t->gcd, t->val);
        }
    }

    void split(pnode t, pnode &l, pnode &r, pii key) {
        if (!t) {
            l = r = nullptr;
        }
        else if (t->key <= key) {
            split(t->r, t->r, r, key), l = t;
        }
        else {
            split(t->l, l, t->l, key), r = t;
        }
        upd(t);
    }

    void merge(pnode &t, pnode l, pnode r) {
        if (!l || !r) {
            t = l ? l : r;
        }
        else if (l->prior > r->prior) {
            merge(l->r, l->r, r), t = l;
        }
        else {
            merge(r->l, l, r->l), t = r;
        }
        upd(t);
    }

    pnode find(pnode t, pii key) {
        if (!t) {
            return nullptr;
        }
        if (t->key == key) {
            return t;
        }
        if (t->key < key) {
            return find(t->r, key);
        }
        else {
            return find(t->l, key);
        }
    }

    void updPath(pnode t, pii key) {
        if (!t) {
            return;
        }
        if (t->key == key) {
            
        }
        else if (t->key < key) {
            updPath(t->r, key);
        }
        else {
            updPath(t->l, key);
        }
        upd(t);
    }

    void insert(pnode &t, pnode it) {
        if (!t) {
            t = it;
        }
        else if (it->prior > t->prior) {
            split(t, it->l, it->r, it->key), t = it;
        }
        else {
            insert(t->key < it->key ? t->r : t->l, it);
        }
        upd(t);
    }

    ll gcdQuery(pnode t, int left, int right) {
        pnode l, m, r;
        split(t, m, r, {right + 1, -1});
        split(m, l, m, {left, -1});

        ll toReturn = m ? m->gcd : 0;

        merge(t, l, m);
        merge(t, t, r);

        return toReturn;
    }

  public:
    Treap() : root(nullptr) {
        srand(time(nullptr));
    }

    ~Treap() {
        clear(this->root);
    }

    void smartInsert(pii key, ll val) {
        pnode found = find(this->root, key);

        if (found) {
            found->val = val;
            updPath(this->root, key);
        }
        else {
            insert(this->root, new Node(key, val));
        }
    }

    ll gcdQuery(int left, int right) {
        return gcdQuery(this->root, left, right);
    }
};

struct Segment {
  private:
    struct Node {
        Treap treap;
        Node *l, *r;

        Node() : treap(Treap()), l(nullptr), r(nullptr) {}
    };
  private:
    typedef struct Node* pnode;
  private:
    pnode root;

    void clear(pnode t) {
        if (t) {
            clear(t->l);
            clear(t->r);
            delete t;
        }
    }

    void update(pnode &t, int x, int y, int l, int r, ll val) {
        if (!t) t = new Node();

        t->treap.smartInsert({y, x}, val);
        if (l == r) return;

        int mid = (l + r) >> 1;

        if (x <= mid) {
            update(t->l, x, y, l, mid, val);
        }
        else {
            update(t->r, x, y, mid + 1, r, val);
        }
    }

    ll query(pnode t, int lx, int ly, int rx, int ry, int l, int r) {
        if (!t) return 0;
        if (l > rx || r < lx) return 0;
        if (lx <= l && r <= rx) {
            return t->treap.gcdQuery(ly, ry);
        }

        int mid = (l + r) >> 1;

        ll ql = query(t->l, lx, ly, rx, ry, l, mid);
        ll qr = query(t->r, lx, ly, rx, ry, mid + 1, r); 

        return gcd2(ql, qr);
    }

  public:
    Segment() : root(nullptr) {
        srand(time(nullptr));
    }

    ~Segment() {
        clear(this->root);
    }

    void update(int x, int y, int val) {
        update(this->root, x, y, 0, 1e9, val);
    }

    ll query(int lx, int ly, int rx, int ry) {
        return query(this->root, lx, ly, rx, ry, 0, 1e9);
    }
};

Segment tree;

void init(int R, int C) {
    
}
void update(int P, int Q, ll K) {
    tree.update(P, Q, K);
}
 
ll calculate(int P, int Q, int U, int V) {
    return tree.query(P, Q, U, V);
}

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