oj.uz

답안 #159833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159833 2019-10-25T01:15:40 Z rama_pang 게임 (IOI13_game) C++14
63 / 100
 3253 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; seg = NULL; }
    };

    Node *root;

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

    void update(Node *n, int tl, int tr, int p, int q, lint x) {
        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) n->lc = new Node();
        if (n->rc == NULL && p > mid) n->rc = new Node();
        if (n->seg == NULL && x > 0) n->seg = new SegmentTreeInside();

        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)? 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, 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)? 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 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 248 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 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 827 ms 12756 KB Output is correct
5 Correct 537 ms 13176 KB Output is correct
6 Correct 771 ms 9976 KB Output is correct
7 Correct 861 ms 9728 KB Output is correct
8 Correct 562 ms 6928 KB Output is correct
9 Correct 867 ms 9976 KB Output is correct
10 Correct 752 ms 9436 KB Output is correct
11 Correct 2 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 376 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 504 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 1262 ms 16220 KB Output is correct
13 Correct 2839 ms 6308 KB Output is correct
14 Correct 414 ms 1164 KB Output is correct
15 Correct 3253 ms 9024 KB Output is correct
16 Correct 332 ms 18604 KB Output is correct
17 Correct 1433 ms 11856 KB Output is correct
18 Correct 2141 ms 18828 KB Output is correct
19 Correct 1881 ms 19028 KB Output is correct
20 Correct 1590 ms 18300 KB Output is correct
21 Correct 2 ms 376 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 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 376 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 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 2 ms 376 KB Output is correct
12 Correct 993 ms 13020 KB Output is correct
13 Correct 534 ms 13104 KB Output is correct
14 Correct 782 ms 9960 KB Output is correct
15 Correct 856 ms 9644 KB Output is correct
16 Correct 555 ms 6776 KB Output is correct
17 Correct 846 ms 9848 KB Output is correct
18 Correct 711 ms 9464 KB Output is correct
19 Correct 1258 ms 16004 KB Output is correct
20 Correct 2764 ms 6484 KB Output is correct
21 Correct 414 ms 1044 KB Output is correct
22 Correct 3236 ms 8988 KB Output is correct
23 Correct 319 ms 18424 KB Output is correct
24 Correct 1370 ms 11684 KB Output is correct
25 Correct 2305 ms 18724 KB Output is correct
26 Correct 2033 ms 19024 KB Output is correct
27 Correct 1873 ms 18448 KB Output is correct
28 Runtime error 1476 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 376 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 380 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 840 ms 12864 KB Output is correct
13 Correct 534 ms 13104 KB Output is correct
14 Correct 782 ms 10024 KB Output is correct
15 Correct 858 ms 9816 KB Output is correct
16 Correct 556 ms 6904 KB Output is correct
17 Correct 847 ms 9744 KB Output is correct
18 Correct 724 ms 9380 KB Output is correct
19 Correct 1268 ms 15996 KB Output is correct
20 Correct 2780 ms 6516 KB Output is correct
21 Correct 414 ms 1016 KB Output is correct
22 Correct 3239 ms 8960 KB Output is correct
23 Correct 319 ms 18552 KB Output is correct
24 Correct 1380 ms 11900 KB Output is correct
25 Correct 2345 ms 18792 KB Output is correct
26 Correct 2070 ms 19064 KB Output is correct
27 Correct 1853 ms 18336 KB Output is correct
28 Runtime error 1487 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -