Submission #159909

#	Time	Username	Problem	Language	Result	Execution time	Memory
159909		rama_pang	Game (IOI13_game)	C++14	100 / 100	5412 ms	76680 KiB

game

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

int R, C;

inline lint gcd(lint X, lint Y) {
    lint tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Treap {
    struct TreapNode {
        lint val, real_val;
        int key, priority;
        int tl, tr;
        TreapNode *l, *r;

        TreapNode(): val(0), real_val(0), key(-1), tl(0), tr(0), l(NULL), r(NULL), priority(rand()) {}

        TreapNode(int k, lint v): key(k), real_val(v), val(v), tl(k), tr(k), l(NULL), r(NULL), priority(rand()) {}

        inline void update() {
            val = real_val; 
            if (l) val = gcd(val, l->val);
            if (r) val = gcd(val, r->val);
            tl = l ? l->tl : key;
            tr = r ? r->tr : key;
        }

    };

    using node = TreapNode *;
    
    node root;

    Treap(): root(NULL) {}

    void split(node t, node &l, node &r, int key) {
        if (!t) 
            l = r = NULL;
        else if (key < t->key) 
            split(t->l, l, t->l, key), r = t;
        else
            split(t->r, t->r, r, key), l = t;
        
        if (t) t->update();
    }

    void merge(node &t, node l, node r) {
        if (!l || !r) 
            t = (l)? l : r;
        else if (l->priority > r->priority)
            merge(l->r, l->r, r), t = l;
        else 
            merge(r->l, l, r->l), t = r;

        if (t) t->update();
    }

    bool find(int key) {
        node t = root;
        
        while (t) {
            if (t->key == key) return true;
            t = (key < t->key)? t->l : t->r;
        }

        return false;
    }

    void update(node t, int key, lint val) {
        if (t->key == key) 
            t->real_val = val;
        else
            update((key < t->key)? t->l : t->r, key, val);
        
        if (t) t->update();
    }

    void insert(int pos, lint val) {
        if (find(pos)) return void(update(root, pos, val));
        node l, r;
        split(root, l, r, pos);
        merge(l, l, new TreapNode(pos, val));
        merge(root, l, r);
    }

    lint query(node t, int le, int ri) {
        if (!t || le > t->tr || ri < t->tl) return 0;
        if (le <= t->tl && t->tr <= ri) return t->val;

        lint res = (le <= t->key && t->key <= ri)? t->real_val : 0; 
        res = gcd(res, query(t->l, le, ri));
        res = gcd(res, query(t->r, le, ri));

        return res;
    }

    inline lint query(int l, int r) {
        return query(root, l, r);
    }

};

struct SegmentTree {
    struct SegmentTreeNode {
        Treap treap;
        SegmentTreeNode *lc, *rc;

        SegmentTreeNode() { lc = rc = NULL; }

    };

    using node = SegmentTreeNode *;

    node root;

    SegmentTree() { root = new SegmentTreeNode(); }

    void update(node n, int tl, int tr, int p, int q, lint x) {
        if (tl == tr) return void(n->treap.insert(q, x));
        if (n->lc == NULL) n->lc = new SegmentTreeNode();
        if (n->rc == NULL) n->rc = new SegmentTreeNode();
        
        int mid = (tl + tr) / 2;  
        if (p <= mid) update(n->lc, tl, mid, p, q, x);
        if (p > mid) update(n->rc, mid + 1, tr, p, q, x);

        lint gcd1 = n->lc->treap.query(q, q);
        lint gcd2 = n->rc->treap.query(q, q);

        n->treap.insert(q, gcd(gcd1, gcd2));
    }

    lint query(node n, int tl, int tr, int le, int ri, int lo, int hi) {
        if (!n || tr < le || tl > ri || tl > tr) return 0;
        if (le <= tl && tr <= ri) return n->treap.query(lo, hi);

        int mid = (tl + tr) / 2;
        lint gcd1 = query(n->lc, tl, mid, le, ri, lo, hi);
        lint gcd2 = query(n->rc, mid + 1, tr, le, ri, lo, hi);

        return gcd(gcd1, gcd2);
    }

};

SegmentTree solver;

void init(int R, int C) {
    srand(time(NULL));
    ::R = R, ::C = C;
}

void update(int P, int Q, lint K) {
    solver.update(solver.root, 0, R - 1, P, Q, K);
}

lint calculate(int P, int Q, int U, int V) {
    return solver.query(solver.root, 0, R - 1, P, U, Q, V);
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In constructor 'Treap::TreapNode::TreapNode()':
game.cpp:23:24: warning: 'Treap::TreapNode::r' will be initialized after [-Wreorder]
         TreapNode *l, *r;
                        ^
game.cpp:21:18: warning:   'int Treap::TreapNode::priority' [-Wreorder]
         int key, priority;
                  ^~~~~~~~
game.cpp:25:9: warning:   when initialized here [-Wreorder]
         TreapNode(): val(0), real_val(0), key(-1), tl(0), tr(0), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~
game.cpp: In constructor 'Treap::TreapNode::TreapNode(int, lint)':
game.cpp:21:13: warning: 'Treap::TreapNode::key' will be initialized after [-Wreorder]
         int key, priority;
             ^~~
game.cpp:20:19: warning:   'lint Treap::TreapNode::real_val' [-Wreorder]
         lint val, real_val;
                   ^~~~~~~~
game.cpp:27:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), tl(k), tr(k), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~
game.cpp:20:19: warning: 'Treap::TreapNode::real_val' will be initialized after [-Wreorder]
         lint val, real_val;
                   ^~~~~~~~
game.cpp:20:14: warning:   'lint Treap::TreapNode::val' [-Wreorder]
         lint val, real_val;
              ^~~
game.cpp:27:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), tl(k), tr(k), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~
game.cpp:23:24: warning: 'Treap::TreapNode::r' will be initialized after [-Wreorder]
         TreapNode *l, *r;
                        ^
game.cpp:21:18: warning:   'int Treap::TreapNode::priority' [-Wreorder]
         int key, priority;
                  ^~~~~~~~
game.cpp:27:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), tl(k), tr(k), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~

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