oj.uz

Submission #159909

# Submission time Handle Problem Language Result Execution time Memory
159909 2019-10-25T11:28:29 Z rama_pang Game (IOI13_game) C++14
100 / 100
 5412 ms 76680 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 835 ms 7064 KB Output is correct
5 Correct 353 ms 7544 KB Output is correct
6 Correct 1078 ms 4316 KB Output is correct
7 Correct 1239 ms 4088 KB Output is correct
8 Correct 734 ms 3512 KB Output is correct
9 Correct 1216 ms 4056 KB Output is correct
10 Correct 1115 ms 3704 KB Output is correct
11 Correct 2 ms 380 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 296 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1146 ms 9452 KB Output is correct
13 Correct 2605 ms 3976 KB Output is correct
14 Correct 340 ms 1036 KB Output is correct
15 Correct 2732 ms 4768 KB Output is correct
16 Correct 472 ms 7288 KB Output is correct
17 Correct 1708 ms 5040 KB Output is correct
18 Correct 2656 ms 7620 KB Output is correct
19 Correct 2277 ms 7932 KB Output is correct
20 Correct 2275 ms 7216 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 252 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 921 ms 7320 KB Output is correct
13 Correct 354 ms 7504 KB Output is correct
14 Correct 1048 ms 4352 KB Output is correct
15 Correct 1217 ms 3784 KB Output is correct
16 Correct 687 ms 3320 KB Output is correct
17 Correct 1221 ms 4156 KB Output is correct
18 Correct 1105 ms 3768 KB Output is correct
19 Correct 1154 ms 9464 KB Output is correct
20 Correct 2699 ms 3900 KB Output is correct
21 Correct 340 ms 976 KB Output is correct
22 Correct 2913 ms 4740 KB Output is correct
23 Correct 481 ms 7396 KB Output is correct
24 Correct 1533 ms 5064 KB Output is correct
25 Correct 2667 ms 7700 KB Output is correct
26 Correct 2408 ms 7888 KB Output is correct
27 Correct 2267 ms 7168 KB Output is correct
28 Correct 792 ms 30852 KB Output is correct
29 Correct 1981 ms 34120 KB Output is correct
30 Correct 3117 ms 24224 KB Output is correct
31 Correct 2831 ms 18724 KB Output is correct
32 Correct 546 ms 1144 KB Output is correct
33 Correct 791 ms 1656 KB Output is correct
34 Correct 701 ms 31084 KB Output is correct
35 Correct 1917 ms 16908 KB Output is correct
36 Correct 3931 ms 31396 KB Output is correct
37 Correct 3148 ms 31604 KB Output is correct
38 Correct 3235 ms 30832 KB Output is correct
39 Correct 2539 ms 24696 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1076 ms 7092 KB Output is correct
13 Correct 360 ms 7340 KB Output is correct
14 Correct 1098 ms 4192 KB Output is correct
15 Correct 1216 ms 3908 KB Output is correct
16 Correct 754 ms 3376 KB Output is correct
17 Correct 1235 ms 4068 KB Output is correct
18 Correct 1117 ms 3576 KB Output is correct
19 Correct 1144 ms 9200 KB Output is correct
20 Correct 2532 ms 3836 KB Output is correct
21 Correct 380 ms 952 KB Output is correct
22 Correct 2584 ms 4652 KB Output is correct
23 Correct 488 ms 7288 KB Output is correct
24 Correct 1499 ms 5084 KB Output is correct
25 Correct 2895 ms 7760 KB Output is correct
26 Correct 2378 ms 7884 KB Output is correct
27 Correct 2475 ms 7260 KB Output is correct
28 Correct 798 ms 31096 KB Output is correct
29 Correct 1990 ms 34000 KB Output is correct
30 Correct 3199 ms 24248 KB Output is correct
31 Correct 2896 ms 18808 KB Output is correct
32 Correct 545 ms 1148 KB Output is correct
33 Correct 773 ms 1528 KB Output is correct
34 Correct 704 ms 30908 KB Output is correct
35 Correct 1896 ms 16820 KB Output is correct
36 Correct 3990 ms 31372 KB Output is correct
37 Correct 3174 ms 31608 KB Output is correct
38 Correct 3356 ms 30840 KB Output is correct
39 Correct 1178 ms 64988 KB Output is correct
40 Correct 3505 ms 67384 KB Output is correct
41 Correct 5071 ms 51156 KB Output is correct
42 Correct 4641 ms 45688 KB Output is correct
43 Correct 1677 ms 72568 KB Output is correct
44 Correct 765 ms 10872 KB Output is correct
45 Correct 2529 ms 34852 KB Output is correct
46 Correct 5412 ms 76680 KB Output is correct
47 Correct 5372 ms 76608 KB Output is correct
48 Correct 5396 ms 76196 KB Output is correct
49 Correct 2 ms 376 KB Output is correct