oj.uz

답안 #261719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261719 2020-08-12T03:00:25 Z smax 게임 (IOI13_game) C++17
37 / 100
 2337 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Node {
    long long ans;
    int l, r;
    Node *left, *right;

    Node() {}

    Node(int _l, int _r) : ans(0), l(_l), r(_r), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Node(l, m);
            right = new Node(m+1, r);
        }
    }
};

long long query(Node *p, int i, int j) {
    if (i > p->r || j < p->l)
        return 0;
    if (i <= p->l && p->r <= j)
        return p->ans;

    p->extend();
    return gcd2(query(p->left, i, j), query(p->right, i, j));
}

void update(Node *p, int idx, long long val) {
    if (p->l == p->r) {
        p->ans = val;
        return;
    }

    p->extend();
    int m = (p->l + p->r) / 2;
    if (idx <= m)
        update(p->left, idx, val);
    else
        update(p->right, idx, val);
    p->ans = gcd2(p->left->ans, p->right->ans);
}

void update_y(Node *cur, Node *curL, Node *curR, int y, long long val) {
    if (cur->l == cur->r) {
        cur->ans = gcd2(curL->ans, curR->ans);
        return;
    }

    cur->extend();
    curL->extend();
    curR->extend();
    int m = (cur->l + cur->r) / 2;
    if (y <= m)
        update_y(cur->left, curL->left, curR->left, y, val);
    else
        update_y(cur->right, curL->right, curR->right, y, val);
    cur->ans = gcd2(cur->left->ans, cur->right->ans);
}

struct Seg {
    int n, l, r;
    Node yNode;
    Seg *left, *right;

    Seg() {}

    Seg(int _n, int _l, int _r) : n(_n), l(_l), r(_r), yNode(0, n-1), left(NULL), right(NULL) {}

    void extend() {
        if (!left) {
            int m = (l + r) / 2;
            left = new Seg(n, l, m);
            right = new Seg(n, m+1, r);
        }
    }
} st;

long long query(Seg *p, int ix, int iy, int jx, int jy) {
    if (ix > p->r || jx < p->l)
        return 0;
    if (ix <= p->l && p->r <= jx)
        return query(&p->yNode, iy, jy);

    p->extend();
    return gcd2(query(p->left, ix, iy, jx, jy), query(p->right, ix, iy, jx, jy));
}

void update(Seg *p, int x, int y, long long val) {
    if (p->l == p->r) {
        update(&p->yNode, y, val);
        return;
    }

    p->extend();
    int m = (p->l + p->r) / 2;
    if (x <= m)
        update(p->left, x, y, val);
    else
        update(p->right, x, y, val);
    update_y(&p->yNode, &p->left->yNode, &p->right->yNode, y, val);
}

void init(int R, int C) {
    st = Seg(C, 0, R - 1);
}

void update(int P, int Q, long long K) {
    update(&st, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query(&st, P, Q, U, 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 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 368 KB Output is correct
12 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1191 ms 47144 KB Output is correct
5 Correct 620 ms 38776 KB Output is correct
6 Correct 1316 ms 111964 KB Output is correct
7 Correct 1306 ms 111608 KB Output is correct
8 Correct 1127 ms 108612 KB Output is correct
9 Correct 1278 ms 112912 KB Output is correct
10 Correct 1277 ms 111200 KB Output is correct
11 Correct 0 ms 256 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 2 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 788 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1264 ms 47924 KB Output is correct
13 Correct 1577 ms 18164 KB Output is correct
14 Correct 911 ms 3704 KB Output is correct
15 Correct 1795 ms 28792 KB Output is correct
16 Correct 319 ms 71164 KB Output is correct
17 Runtime error 2203 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 2 ms 896 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1291 ms 47224 KB Output is correct
13 Correct 608 ms 38776 KB Output is correct
14 Correct 1285 ms 111936 KB Output is correct
15 Correct 1297 ms 111644 KB Output is correct
16 Correct 1125 ms 108696 KB Output is correct
17 Correct 1263 ms 113280 KB Output is correct
18 Correct 1239 ms 111148 KB Output is correct
19 Correct 1244 ms 48072 KB Output is correct
20 Correct 1578 ms 18292 KB Output is correct
21 Correct 937 ms 3800 KB Output is correct
22 Correct 1787 ms 28920 KB Output is correct
23 Correct 316 ms 71032 KB Output is correct
24 Runtime error 2154 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 896 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 768 KB Output is correct
7 Correct 1 ms 288 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 672 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1260 ms 47176 KB Output is correct
13 Correct 627 ms 38776 KB Output is correct
14 Correct 1303 ms 111992 KB Output is correct
15 Correct 1318 ms 111616 KB Output is correct
16 Correct 1153 ms 108540 KB Output is correct
17 Correct 1337 ms 112888 KB Output is correct
18 Correct 1271 ms 111096 KB Output is correct
19 Correct 1305 ms 47800 KB Output is correct
20 Correct 1559 ms 18300 KB Output is correct
21 Correct 918 ms 3704 KB Output is correct
22 Correct 1829 ms 28920 KB Output is correct
23 Correct 331 ms 71032 KB Output is correct
24 Runtime error 2337 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -