oj.uz

Submission #159906

# Submission time Handle Problem Language Result Execution time Memory
159906 2019-10-25T11:18:42 Z rama_pang Game (IOI13_game) C++14
80 / 100
 13000 ms 56536 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;
        TreapNode *l, *r;

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

        TreapNode(int k, lint v): key(k), real_val(v), val(v), 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);
        }

    };

    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) {
    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:22: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:24:9: warning:   when initialized here [-Wreorder]
         TreapNode(): val(0), real_val(0), key(-1), 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:26:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), 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:26:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~
game.cpp:22: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:26:9: warning:   when initialized here [-Wreorder]
         TreapNode(int k, lint v): key(k), real_val(v), val(v), l(NULL), r(NULL), priority(rand()) {}
         ^~~~~~~~~

Subtask #1
10.0 / 10.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 4 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 4 ms 380 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 420 KB Output is correct
10 Correct 3 ms 380 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 252 KB Output is correct
4 Correct 1478 ms 6732 KB Output is correct
5 Correct 590 ms 6776 KB Output is correct
6 Correct 3089 ms 3568 KB Output is correct
7 Correct 3526 ms 3412 KB Output is correct
8 Correct 2412 ms 3100 KB Output is correct
9 Correct 3388 ms 3316 KB Output is correct
10 Correct 3164 ms 3036 KB Output is correct
11 Correct 2 ms 252 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 5 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 376 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 376 KB Output is correct
12 Correct 1898 ms 8352 KB Output is correct
13 Correct 7492 ms 3376 KB Output is correct
14 Correct 967 ms 1016 KB Output is correct
15 Correct 7744 ms 4024 KB Output is correct
16 Correct 1067 ms 5752 KB Output is correct
17 Correct 5421 ms 4324 KB Output is correct
18 Correct 9427 ms 6212 KB Output is correct
19 Correct 8066 ms 6364 KB Output is correct
20 Correct 8857 ms 5856 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 256 KB Output is correct
2 Correct 5 ms 504 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 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 3 ms 376 KB Output is correct
12 Correct 1437 ms 6616 KB Output is correct
13 Correct 614 ms 6776 KB Output is correct
14 Correct 3079 ms 3552 KB Output is correct
15 Correct 3405 ms 3228 KB Output is correct
16 Correct 2392 ms 3272 KB Output is correct
17 Correct 3459 ms 3576 KB Output is correct
18 Correct 3365 ms 3048 KB Output is correct
19 Correct 1979 ms 8312 KB Output is correct
20 Correct 7114 ms 3216 KB Output is correct
21 Correct 952 ms 1052 KB Output is correct
22 Correct 7586 ms 3980 KB Output is correct
23 Correct 1044 ms 5900 KB Output is correct
24 Correct 5380 ms 4388 KB Output is correct
25 Correct 9412 ms 6304 KB Output is correct
26 Correct 8010 ms 6340 KB Output is correct
27 Correct 8623 ms 5728 KB Output is correct
28 Correct 2896 ms 26096 KB Output is correct
29 Correct 3159 ms 29168 KB Output is correct
30 Correct 9492 ms 19788 KB Output is correct
31 Correct 8103 ms 15464 KB Output is correct
32 Correct 1257 ms 1144 KB Output is correct
33 Correct 2165 ms 1528 KB Output is correct
34 Correct 1733 ms 26332 KB Output is correct
35 Correct 5819 ms 14456 KB Output is correct
36 Correct 10722 ms 26540 KB Output is correct
37 Correct 8747 ms 26732 KB Output is correct
38 Correct 10301 ms 26308 KB Output is correct
39 Correct 7468 ms 20920 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 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 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 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 6 ms 376 KB Output is correct
12 Correct 1375 ms 6592 KB Output is correct
13 Correct 580 ms 6788 KB Output is correct
14 Correct 2974 ms 3584 KB Output is correct
15 Correct 3506 ms 3420 KB Output is correct
16 Correct 2293 ms 3180 KB Output is correct
17 Correct 3373 ms 3508 KB Output is correct
18 Correct 3175 ms 3164 KB Output is correct
19 Correct 1970 ms 8156 KB Output is correct
20 Correct 7134 ms 3392 KB Output is correct
21 Correct 952 ms 1176 KB Output is correct
22 Correct 8004 ms 3960 KB Output is correct
23 Correct 1194 ms 5824 KB Output is correct
24 Correct 5324 ms 4220 KB Output is correct
25 Correct 9514 ms 6236 KB Output is correct
26 Correct 7820 ms 6400 KB Output is correct
27 Correct 8786 ms 5720 KB Output is correct
28 Correct 2655 ms 25976 KB Output is correct
29 Correct 3306 ms 29256 KB Output is correct
30 Correct 9733 ms 19924 KB Output is correct
31 Correct 8284 ms 15368 KB Output is correct
32 Correct 1247 ms 932 KB Output is correct
33 Correct 2085 ms 1476 KB Output is correct
34 Correct 1737 ms 26168 KB Output is correct
35 Correct 5966 ms 14448 KB Output is correct
36 Correct 11158 ms 26576 KB Output is correct
37 Correct 8817 ms 26852 KB Output is correct
38 Correct 10361 ms 26140 KB Output is correct
39 Correct 3583 ms 54480 KB Output is correct
40 Correct 5572 ms 56536 KB Output is correct
41 Execution timed out 13012 ms 40244 KB Time limit exceeded
42 Halted 0 ms 0 KB -