oj.uz

Submission #159837

# Submission time Handle Problem Language Result Execution time Memory
159837 2019-10-25T01:20:16 Z rama_pang Game (IOI13_game) C++14
63 / 100
 3283 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 && x > 0) n->lc = new NodeInside();
        if (n->rc == NULL && p > mid && x > 0) n->rc = new NodeInside();

        if (p <= mid && n->lc) update(n->lc, tl, mid, p, x);
        if (p > mid && n->rc) 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; seg = NULL; }
    };

    Node *root;

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

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

        int mid = (tl + tr) / 2;  
        if (n->lc == NULL && p <= mid && x > 0) n->lc = new Node();
        if (n->rc == NULL && p > mid && x > 0) n->rc = new Node();
        if (n->seg == NULL && x > 0) n->seg = new SegmentTreeInside();

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

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

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

        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 376 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 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 3 ms 504 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 2 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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 816 ms 12732 KB Output is correct
5 Correct 514 ms 13032 KB Output is correct
6 Correct 762 ms 9928 KB Output is correct
7 Correct 963 ms 9896 KB Output is correct
8 Correct 550 ms 6872 KB Output is correct
9 Correct 818 ms 9844 KB Output is correct
10 Correct 676 ms 9548 KB Output is correct
11 Correct 2 ms 376 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 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 380 KB Output is correct
6 Correct 2 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 372 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 1250 ms 16128 KB Output is correct
13 Correct 2855 ms 6452 KB Output is correct
14 Correct 416 ms 1060 KB Output is correct
15 Correct 3254 ms 9080 KB Output is correct
16 Correct 301 ms 18440 KB Output is correct
17 Correct 1287 ms 11764 KB Output is correct
18 Correct 2244 ms 18948 KB Output is correct
19 Correct 2250 ms 19064 KB Output is correct
20 Correct 1895 ms 18396 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 256 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 252 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 256 KB Output is correct
9 Correct 3 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 824 ms 12776 KB Output is correct
13 Correct 530 ms 13100 KB Output is correct
14 Correct 788 ms 10148 KB Output is correct
15 Correct 853 ms 9848 KB Output is correct
16 Correct 561 ms 6776 KB Output is correct
17 Correct 832 ms 9880 KB Output is correct
18 Correct 741 ms 9388 KB Output is correct
19 Correct 1255 ms 16156 KB Output is correct
20 Correct 2952 ms 6448 KB Output is correct
21 Correct 417 ms 1016 KB Output is correct
22 Correct 3283 ms 9164 KB Output is correct
23 Correct 314 ms 18528 KB Output is correct
24 Correct 1444 ms 11804 KB Output is correct
25 Correct 2304 ms 18856 KB Output is correct
26 Correct 2033 ms 19008 KB Output is correct
27 Correct 1722 ms 18448 KB Output is correct
28 Runtime error 1515 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 380 KB Output is correct
3 Correct 3 ms 504 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 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 504 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 812 ms 12720 KB Output is correct
13 Correct 527 ms 13048 KB Output is correct
14 Correct 783 ms 9872 KB Output is correct
15 Correct 868 ms 9732 KB Output is correct
16 Correct 539 ms 6784 KB Output is correct
17 Correct 905 ms 9848 KB Output is correct
18 Correct 727 ms 9336 KB Output is correct
19 Correct 1247 ms 16032 KB Output is correct
20 Correct 2862 ms 6428 KB Output is correct
21 Correct 418 ms 1160 KB Output is correct
22 Correct 3270 ms 9052 KB Output is correct
23 Correct 318 ms 18424 KB Output is correct
24 Correct 1440 ms 11820 KB Output is correct
25 Correct 2459 ms 18888 KB Output is correct
26 Correct 1871 ms 19092 KB Output is correct
27 Correct 1794 ms 18416 KB Output is correct
28 Runtime error 1490 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -