oj.uz

Submission #159820

# Submission time Handle Problem Language Result Execution time Memory
159820 2019-10-24T23:53:56 Z rama_pang Game (IOI13_game) C++14
63 / 100
 4022 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;
        }

        if (n->lc == NULL) n->lc = new NodeInside();
        if (n->rc == NULL) n->rc = new NodeInside();
        
        lint mid = (tl + tr) / 2ll;
        if (p <= mid) 
            update(n->lc, tl, mid, p, x);
        else
            update(n->rc, mid + 1, tr, p, x);

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

    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;
        if (n->lc == NULL) n->lc = new NodeInside();
        if (n->rc == NULL) n->rc = new NodeInside();

        lint gcd1 = query(n->lc, tl, mid, le, ri); 
        lint gcd2 = query(n->rc, mid + 1, tr, le, ri);
        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;
        }

        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();
        
        lint mid = (tl + tr) / 2;        
        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->seg.query(n->lc->seg.root, 0, C - 1, q, q);
        lint gcd2 = n->rc->seg.query(n->rc->seg.root, 0, C - 1, q, q);
        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);

        lint mid = (tl + tr) / 2;
        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();

        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;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 632 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 632 KB Output is correct
10 Correct 3 ms 504 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 504 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 1215 ms 36932 KB Output is correct
5 Correct 687 ms 30824 KB Output is correct
6 Correct 1298 ms 79220 KB Output is correct
7 Correct 1252 ms 79028 KB Output is correct
8 Correct 1057 ms 76664 KB Output is correct
9 Correct 1322 ms 79856 KB Output is correct
10 Correct 1204 ms 78456 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 384 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 632 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 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1457 ms 37080 KB Output is correct
13 Correct 2758 ms 16004 KB Output is correct
14 Correct 979 ms 6868 KB Output is correct
15 Correct 3174 ms 23352 KB Output is correct
16 Correct 384 ms 51320 KB Output is correct
17 Correct 3326 ms 215200 KB Output is correct
18 Correct 3908 ms 225520 KB Output is correct
19 Correct 3802 ms 225400 KB Output is correct
20 Correct 3763 ms 224680 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 384 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 3 ms 632 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 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 376 KB Output is correct
12 Correct 1212 ms 36668 KB Output is correct
13 Correct 713 ms 30872 KB Output is correct
14 Correct 1279 ms 79172 KB Output is correct
15 Correct 1265 ms 78836 KB Output is correct
16 Correct 1068 ms 76704 KB Output is correct
17 Correct 1304 ms 79824 KB Output is correct
18 Correct 1137 ms 78440 KB Output is correct
19 Correct 1461 ms 37112 KB Output is correct
20 Correct 2645 ms 15984 KB Output is correct
21 Correct 957 ms 6876 KB Output is correct
22 Correct 3107 ms 23520 KB Output is correct
23 Correct 385 ms 51568 KB Output is correct
24 Correct 3343 ms 215032 KB Output is correct
25 Correct 4022 ms 225448 KB Output is correct
26 Correct 3789 ms 225348 KB Output is correct
27 Correct 3702 ms 224720 KB Output is correct
28 Runtime error 520 ms 256004 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 384 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 488 KB Output is correct
6 Correct 3 ms 632 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 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1172 ms 36740 KB Output is correct
13 Correct 689 ms 30764 KB Output is correct
14 Correct 1289 ms 79208 KB Output is correct
15 Correct 1295 ms 78956 KB Output is correct
16 Correct 1080 ms 76660 KB Output is correct
17 Correct 1348 ms 79876 KB Output is correct
18 Correct 1193 ms 78440 KB Output is correct
19 Correct 1464 ms 37056 KB Output is correct
20 Correct 2679 ms 15864 KB Output is correct
21 Correct 976 ms 6672 KB Output is correct
22 Correct 3156 ms 23504 KB Output is correct
23 Correct 383 ms 51400 KB Output is correct
24 Correct 3362 ms 215128 KB Output is correct
25 Correct 3950 ms 225356 KB Output is correct
26 Correct 3846 ms 225428 KB Output is correct
27 Correct 3602 ms 224936 KB Output is correct
28 Runtime error 531 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -