oj.uz

Submission #159821

# Submission time Handle Problem Language Result Execution time Memory
159821 2019-10-25T00:00:55 Z rama_pang Game (IOI13_game) C++14
63 / 100
 3228 ms 256004 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 SegmentTreeInside {
    struct NodeInside {
        lint val;
        NodeInside *lc, *rc;

        NodeInside(): val(0), lc(NULL), rc(NULL) {}
    };

    NodeInside *root;

    SegmentTreeInside() { root = new NodeInside(); }

    void update(NodeInside *n, int tl, int tr, int p, lint x) {
        if (tl == tr) {
            n->val = x;
            return;
        }


        int mid = (tl + tr) / 2;
        if (n->lc == NULL && p <= mid) n->lc = new NodeInside();
        if (n->rc == NULL && p > mid) n->rc = new NodeInside();

        if (p <= mid) 
            update(n->lc, tl, mid, p, x);
        else
            update(n->rc, mid + 1, tr, p, x);


        n->val = gcd((n->lc)? n->lc->val : 0, (n->rc)? n->rc->val : 0);   
    }

    lint query(NodeInside *n, int tl, int tr, int le, int ri) {
        if (tr < le || tl > ri || tl > tr) return 0;
        if (le <= tl && tr <= ri) return n->val;
        
        int mid = (tl + tr) / 2;
        lint gcd1 = (n->lc)? query(n->lc, tl, mid, le, ri) : 0; 
        lint gcd2 = (n->rc)? query(n->rc, mid + 1, tr, le, ri) : 0;
        return gcd(gcd1, gcd2);
    }

};

struct SegmentTree {
    struct Node {
        SegmentTreeInside seg;
        Node *lc, *rc;

        Node() {
            lc = rc = NULL;
        }
    };

    Node *root;

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

    void update(Node *n, int tl, int tr, int p, int q, lint x) {
        if (tl == tr) {
            n->seg.update(n->seg.root, 0, C - 1, q, x);
            return;
        }

        int mid = (tl + tr) / 2;  
        if (n->lc == NULL && p <= mid) n->lc = new Node();
        if (n->rc == NULL && p > mid) n->rc = new Node();
        
        if (p <= mid) 
            update(n->lc, tl, mid, p, q, x);
        else
            update(n->rc, mid + 1, tr, p, q, x);

        lint gcd1 = (n->lc)? n->lc->seg.query(n->lc->seg.root, 0, C - 1, q, q) : 0;
        lint gcd2 = (n->rc)? n->rc->seg.query(n->rc->seg.root, 0, C - 1, q, q) : 0;
        n->seg.update(n->seg.root, 0, C - 1, q, gcd(gcd1, gcd2));
    }

    lint query(Node *n, lint tl, lint tr, lint le, lint ri, lint lo, lint hi) {
        if (tr < le || tl > ri || tl > tr) return 0;
        if (le <= tl && tr <= ri) return n->seg.query(n->seg.root, 0, C - 1, lo, hi);

        int mid = (tl + tr) / 2;
        lint gcd1 = (n->lc)? query(n->lc, tl, mid, le, ri, lo, hi) : 0;
        lint gcd2 = (n->rc)? query(n->rc, mid + 1, tr, le, ri, lo, hi) : 0;
        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;
      ^~~

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 248 KB Output is correct
3 Correct 3 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 3 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 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 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 376 KB Output is correct
4 Correct 798 ms 12792 KB Output is correct
5 Correct 535 ms 13116 KB Output is correct
6 Correct 804 ms 10084 KB Output is correct
7 Correct 842 ms 9848 KB Output is correct
8 Correct 536 ms 6764 KB Output is correct
9 Correct 803 ms 9988 KB Output is correct
10 Correct 735 ms 9376 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 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 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 504 KB Output is correct
7 Correct 2 ms 376 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 376 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1262 ms 15880 KB Output is correct
13 Correct 2776 ms 6380 KB Output is correct
14 Correct 414 ms 988 KB Output is correct
15 Correct 3228 ms 8956 KB Output is correct
16 Correct 318 ms 18268 KB Output is correct
17 Correct 1368 ms 11652 KB Output is correct
18 Correct 2513 ms 18828 KB Output is correct
19 Correct 1993 ms 18956 KB Output is correct
20 Correct 1786 ms 18216 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 380 KB Output is correct
3 Correct 3 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 3 ms 372 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 813 ms 12868 KB Output is correct
13 Correct 530 ms 13064 KB Output is correct
14 Correct 782 ms 10028 KB Output is correct
15 Correct 857 ms 9684 KB Output is correct
16 Correct 552 ms 6904 KB Output is correct
17 Correct 821 ms 9976 KB Output is correct
18 Correct 716 ms 9384 KB Output is correct
19 Correct 1258 ms 16036 KB Output is correct
20 Correct 2753 ms 6196 KB Output is correct
21 Correct 413 ms 1020 KB Output is correct
22 Correct 3216 ms 8908 KB Output is correct
23 Correct 320 ms 18424 KB Output is correct
24 Correct 1300 ms 11768 KB Output is correct
25 Correct 2161 ms 18716 KB Output is correct
26 Correct 1934 ms 18904 KB Output is correct
27 Correct 1731 ms 18200 KB Output is correct
28 Correct 1460 ms 256000 KB Output is correct
29 Runtime error 2549 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 504 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 504 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 833 ms 12792 KB Output is correct
13 Correct 545 ms 13016 KB Output is correct
14 Correct 778 ms 10096 KB Output is correct
15 Correct 894 ms 9760 KB Output is correct
16 Correct 545 ms 6904 KB Output is correct
17 Correct 830 ms 9892 KB Output is correct
18 Correct 737 ms 9372 KB Output is correct
19 Correct 1251 ms 15932 KB Output is correct
20 Correct 2869 ms 6308 KB Output is correct
21 Correct 416 ms 1116 KB Output is correct
22 Correct 3220 ms 8976 KB Output is correct
23 Correct 310 ms 18424 KB Output is correct
24 Correct 1462 ms 11692 KB Output is correct
25 Correct 2287 ms 18780 KB Output is correct
26 Correct 2116 ms 18904 KB Output is correct
27 Correct 1704 ms 18320 KB Output is correct
28 Correct 1474 ms 256000 KB Output is correct
29 Runtime error 2674 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -