oj.uz

Submission #159903

# Submission time Handle Problem Language Result Execution time Memory
159903 2019-10-25T11:04:41 Z rama_pang Game (IOI13_game) C++14
80 / 100
 13000 ms 67152 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;
}

inline int rng() {
    int res = rand();
    res = res ^ (res >> 16) * 913578246;
    res = res ^ (res >> 16) * 192837465;
    res = res ^ (res >> 16);
    return res;
}

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

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

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

        inline void update() {
            val = real_val; 
            if (l) val = gcd(val, l->val);
            if (r) val = gcd(val, r->val);
        }

    };

    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(int l, int r) {
        if (!root) return 0;
        node lt, rt, t;
        split(root, lt, t, l - 1);
        split(t, t, rt, r);
        lint res = (t)? t->val : 0;
        merge(root, lt, t);
        merge(root, root, rt);
        return res;
    }

};

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) {
    ::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:30:24: warning: 'Treap::TreapNode::r' will be initialized after [-Wreorder]
         TreapNode *l, *r;
                        ^
game.cpp:29:18: warning:   'int Treap::TreapNode::priority' [-Wreorder]
         int key, priority;
                  ^~~~~~~~
game.cpp:32:9: warning:   when initialized here [-Wreorder]
         TreapNode(): val(0), real_val(0), key(-1), l(NULL), r(NULL), priority(rng()) {}
         ^~~~~~~~~
game.cpp: In constructor 'Treap::TreapNode::TreapNode(int, lint)':
game.cpp:29:13: warning: 'Treap::TreapNode::key' will be initialized after [-Wreorder]
         int key, priority;
             ^~~
game.cpp:28:19: warning:   'lint Treap::TreapNode::real_val' [-Wreorder]
         lint val, real_val;
                   ^~~~~~~~
game.cpp:34:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), l(NULL), r(NULL), priority(rng()) {}
         ^~~~~~~~~
game.cpp:28:19: warning: 'Treap::TreapNode::real_val' will be initialized after [-Wreorder]
         lint val, real_val;
                   ^~~~~~~~
game.cpp:28:14: warning:   'lint Treap::TreapNode::val' [-Wreorder]
         lint val, real_val;
              ^~~
game.cpp:34:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), l(NULL), r(NULL), priority(rng()) {}
         ^~~~~~~~~
game.cpp:30:24: warning: 'Treap::TreapNode::r' will be initialized after [-Wreorder]
         TreapNode *l, *r;
                        ^
game.cpp:29:18: warning:   'int Treap::TreapNode::priority' [-Wreorder]
         int key, priority;
                  ^~~~~~~~
game.cpp:34:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), l(NULL), r(NULL), priority(rng()) {}
         ^~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 1512 ms 6656 KB Output is correct
5 Correct 613 ms 6696 KB Output is correct
6 Correct 3060 ms 3608 KB Output is correct
7 Correct 3426 ms 3408 KB Output is correct
8 Correct 2306 ms 3064 KB Output is correct
9 Correct 3454 ms 3352 KB Output is correct
10 Correct 3107 ms 3112 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 380 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 256 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 2005 ms 8212 KB Output is correct
13 Correct 7071 ms 3420 KB Output is correct
14 Correct 920 ms 1144 KB Output is correct
15 Correct 7530 ms 3888 KB Output is correct
16 Correct 1025 ms 5688 KB Output is correct
17 Correct 5194 ms 4212 KB Output is correct
18 Correct 9139 ms 6136 KB Output is correct
19 Correct 7961 ms 6368 KB Output is correct
20 Correct 8665 ms 5832 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 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 380 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 380 KB Output is correct
12 Correct 1512 ms 6576 KB Output is correct
13 Correct 601 ms 6776 KB Output is correct
14 Correct 3058 ms 3668 KB Output is correct
15 Correct 3441 ms 3256 KB Output is correct
16 Correct 2406 ms 3036 KB Output is correct
17 Correct 3560 ms 3304 KB Output is correct
18 Correct 3230 ms 2920 KB Output is correct
19 Correct 2061 ms 8268 KB Output is correct
20 Correct 7132 ms 3424 KB Output is correct
21 Correct 947 ms 1224 KB Output is correct
22 Correct 7624 ms 4004 KB Output is correct
23 Correct 1031 ms 5880 KB Output is correct
24 Correct 5253 ms 4340 KB Output is correct
25 Correct 9144 ms 6176 KB Output is correct
26 Correct 7886 ms 6484 KB Output is correct
27 Correct 8530 ms 5796 KB Output is correct
28 Correct 2693 ms 32208 KB Output is correct
29 Correct 3237 ms 39324 KB Output is correct
30 Correct 9309 ms 26876 KB Output is correct
31 Correct 8560 ms 22544 KB Output is correct
32 Correct 1284 ms 10232 KB Output is correct
33 Correct 2151 ms 10604 KB Output is correct
34 Correct 1672 ms 32988 KB Output is correct
35 Correct 6261 ms 24308 KB Output is correct
36 Correct 10853 ms 37176 KB Output is correct
37 Correct 9235 ms 37420 KB Output is correct
38 Correct 10634 ms 36948 KB Output is correct
39 Correct 7500 ms 31336 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.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 5 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 4 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 4 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 1507 ms 6492 KB Output is correct
13 Correct 609 ms 6784 KB Output is correct
14 Correct 3128 ms 3680 KB Output is correct
15 Correct 3450 ms 3320 KB Output is correct
16 Correct 2289 ms 3076 KB Output is correct
17 Correct 3404 ms 3424 KB Output is correct
18 Correct 3181 ms 2896 KB Output is correct
19 Correct 2036 ms 8216 KB Output is correct
20 Correct 7598 ms 3312 KB Output is correct
21 Correct 893 ms 1068 KB Output is correct
22 Correct 7556 ms 3972 KB Output is correct
23 Correct 1039 ms 5848 KB Output is correct
24 Correct 5245 ms 4216 KB Output is correct
25 Correct 9252 ms 6260 KB Output is correct
26 Correct 7812 ms 6304 KB Output is correct
27 Correct 8467 ms 5708 KB Output is correct
28 Correct 2701 ms 32208 KB Output is correct
29 Correct 3218 ms 39216 KB Output is correct
30 Correct 9440 ms 26892 KB Output is correct
31 Correct 8531 ms 22496 KB Output is correct
32 Correct 1284 ms 10360 KB Output is correct
33 Correct 2221 ms 10744 KB Output is correct
34 Correct 1689 ms 33116 KB Output is correct
35 Correct 5979 ms 24312 KB Output is correct
36 Correct 11230 ms 37120 KB Output is correct
37 Correct 8938 ms 37220 KB Output is correct
38 Correct 10571 ms 36844 KB Output is correct
39 Correct 3632 ms 65340 KB Output is correct
40 Correct 5679 ms 67152 KB Output is correct
41 Execution timed out 13086 ms 46960 KB Time limit exceeded
42 Halted 0 ms 0 KB -