oj.uz

Submission #1075883

# Submission time Handle Problem Language Result Execution time Memory
1075883 2024-08-26T09:37:22 Z mc061 Game (IOI13_game) C++17
63 / 100
 1140 ms 152216 KB 
#pragma once

#include <bits/stdc++.h>
#include "game.h"
using namespace std;

const int SZ = 1e9+1;

struct smallnode {
    long long ans;
    int left, right;
    smallnode() {
        ans = 0, left = -1, right = -1;
    }
};
smallnode smalls[1<<22];
int nxt_free = 0;
int create() {
    smalls[nxt_free] = smallnode();
    return nxt_free++;
}

struct bignode {
    int left, right;
    int root;
    bignode() {
        root = -1, left = -1, right = -1;
    }
    void update(int idx, long long val, int x = 0, int tl = 0, int tr = SZ) {
        if (tl == tr) {
            smalls[x].ans = val;
            return;
        }
        int m = (tl + tr) >> 1;
        if (idx <= m) {
            if (smalls[x].left == -1) {
                smalls[x].left = create();
            }
            update(idx, val, smalls[x].left, tl, m);
        }
        else {
            if (smalls[x].right == -1) {
                smalls[x].right = create();
            }
            update(idx, val, smalls[x].right, m+1, tr);
        }
        smalls[x].ans = (smalls[x].left == -1 ? 0 : smalls[smalls[x].left].ans);
        smalls[x].ans = __gcd(smalls[x].ans, (smalls[x].right == -1 ? 0 : smalls[smalls[x].right].ans));
    }
    long long query(int l, int r, int x = 0, int tl = 0, int tr = SZ) {
        if (tl >= l && tr <= r) return smalls[x].ans;
        if (tr < l || tl > r) return 0;
        int m = (tl + tr) >> 1;
        long long from_r = (smalls[x].right == -1 ? 0 : query(l, r, smalls[x].right, m+1, tr));
        long long from_l = (smalls[x].left == -1 ? 0 : query(l, r, smalls[x].left, tl, m));
        return __gcd(from_l, from_r);
    }
};
bignode bigs[1<<19];
int nxt_free_big = 0;
int create_big() {
    bigs[nxt_free_big] = bignode();
    bigs[nxt_free_big].root = create();
    return nxt_free_big++;
}

struct segtree {
    void update(int i, int j, long long val, int x = 0, int tl = 0, int tr = SZ) {
        if (tl == tr) {
            bigs[x].update(j, val, bigs[x].root);
            return;
        }
        int m = (tl + tr) >> 1;
        if (i <= m) {
            if (bigs[x].left == -1) {
                bigs[x].left = create_big();
            }
            update(i, j, val, bigs[x].left, tl, m);
        }
        else {
            if (bigs[x].right == -1) {
                bigs[x].right = create_big();
            }
            update(i, j, val, bigs[x].right, m+1, tr);
        }
        long long from_l = (bigs[x].left == -1 ? 0 : bigs[bigs[x].left].query(j, j, bigs[bigs[x].left].root));
        long long from_r = (bigs[x].right == -1 ? 0 : bigs[bigs[x].right].query(j, j, bigs[bigs[x].right].root));
        bigs[x].update(j, __gcd(from_l, from_r), bigs[x].root);
    }
    long long query(int l, int r, int jl, int jr, int x = 0, int tl = 0, int tr = SZ) {
        if (tl >= l && tr <= r) {
            return bigs[x].query(jl, jr, bigs[x].root);
        }
        if (tl > r || l > tr) return 0;
        int m = (tl + tr) >> 1;
        long long from_l = 0;
        long long from_r = 0;
        if (bigs[x].left != -1) from_l = query(l, r, jl, jr, bigs[x].left, tl, m);
        if (bigs[x].right != -1) from_r = query(l, r, jl, jr, bigs[x].right, m+1, tr);
        return __gcd(from_l, from_r);
    }
};

const int SQ = 1e3+1;
segtree now;

void init(int R, int C) {
    create_big();
}
void update(int P, int Q, long long K) {
    now.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
    return now.query(P, U, Q, V);
}

Compilation message

game.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 72024 KB Output is correct
2 Correct 26 ms 72020 KB Output is correct
3 Correct 19 ms 72028 KB Output is correct
4 Correct 25 ms 72204 KB Output is correct
5 Correct 18 ms 72028 KB Output is correct
6 Correct 18 ms 72024 KB Output is correct
7 Correct 20 ms 72028 KB Output is correct
8 Correct 19 ms 72028 KB Output is correct
9 Correct 23 ms 72248 KB Output is correct
10 Correct 22 ms 72016 KB Output is correct
11 Correct 21 ms 72248 KB Output is correct
12 Correct 19 ms 72160 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 72188 KB Output is correct
2 Correct 20 ms 72224 KB Output is correct
3 Correct 22 ms 72012 KB Output is correct
4 Correct 515 ms 80576 KB Output is correct
5 Correct 458 ms 80292 KB Output is correct
6 Correct 519 ms 77952 KB Output is correct
7 Correct 503 ms 77456 KB Output is correct
8 Correct 355 ms 77952 KB Output is correct
9 Correct 476 ms 77652 KB Output is correct
10 Correct 448 ms 77236 KB Output is correct
11 Correct 18 ms 72028 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 72028 KB Output is correct
2 Correct 20 ms 72024 KB Output is correct
3 Correct 17 ms 72028 KB Output is correct
4 Correct 16 ms 72028 KB Output is correct
5 Correct 19 ms 72028 KB Output is correct
6 Correct 20 ms 72024 KB Output is correct
7 Correct 22 ms 72108 KB Output is correct
8 Correct 17 ms 72252 KB Output is correct
9 Correct 17 ms 72140 KB Output is correct
10 Correct 20 ms 72016 KB Output is correct
11 Correct 17 ms 72208 KB Output is correct
12 Correct 763 ms 80528 KB Output is correct
13 Correct 962 ms 76880 KB Output is correct
14 Correct 375 ms 77424 KB Output is correct
15 Correct 1140 ms 77240 KB Output is correct
16 Correct 417 ms 77076 KB Output is correct
17 Correct 718 ms 78396 KB Output is correct
18 Correct 1073 ms 78680 KB Output is correct
19 Correct 993 ms 78740 KB Output is correct
20 Correct 921 ms 78140 KB Output is correct
21 Correct 18 ms 72028 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 72024 KB Output is correct
2 Correct 18 ms 72028 KB Output is correct
3 Correct 17 ms 72028 KB Output is correct
4 Correct 18 ms 72172 KB Output is correct
5 Correct 15 ms 72028 KB Output is correct
6 Correct 17 ms 72152 KB Output is correct
7 Correct 17 ms 72028 KB Output is correct
8 Correct 17 ms 72208 KB Output is correct
9 Correct 26 ms 72028 KB Output is correct
10 Correct 18 ms 72028 KB Output is correct
11 Correct 18 ms 72024 KB Output is correct
12 Correct 461 ms 80476 KB Output is correct
13 Correct 413 ms 80296 KB Output is correct
14 Correct 470 ms 77892 KB Output is correct
15 Correct 468 ms 77472 KB Output is correct
16 Correct 340 ms 77928 KB Output is correct
17 Correct 482 ms 77584 KB Output is correct
18 Correct 555 ms 77392 KB Output is correct
19 Correct 754 ms 80208 KB Output is correct
20 Correct 1080 ms 76676 KB Output is correct
21 Correct 363 ms 77336 KB Output is correct
22 Correct 1088 ms 77360 KB Output is correct
23 Correct 378 ms 77052 KB Output is correct
24 Correct 758 ms 78256 KB Output is correct
25 Correct 1045 ms 78408 KB Output is correct
26 Correct 919 ms 78676 KB Output is correct
27 Correct 861 ms 78084 KB Output is correct
28 Runtime error 226 ms 152216 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 72028 KB Output is correct
2 Correct 19 ms 72028 KB Output is correct
3 Correct 20 ms 72100 KB Output is correct
4 Correct 19 ms 72024 KB Output is correct
5 Correct 19 ms 72028 KB Output is correct
6 Correct 20 ms 72028 KB Output is correct
7 Correct 17 ms 72024 KB Output is correct
8 Correct 17 ms 72024 KB Output is correct
9 Correct 17 ms 72028 KB Output is correct
10 Correct 17 ms 72028 KB Output is correct
11 Correct 17 ms 72260 KB Output is correct
12 Correct 434 ms 80468 KB Output is correct
13 Correct 338 ms 80464 KB Output is correct
14 Correct 441 ms 77908 KB Output is correct
15 Correct 452 ms 77504 KB Output is correct
16 Correct 366 ms 77968 KB Output is correct
17 Correct 523 ms 77864 KB Output is correct
18 Correct 434 ms 77392 KB Output is correct
19 Correct 743 ms 80336 KB Output is correct
20 Correct 946 ms 76828 KB Output is correct
21 Correct 382 ms 77596 KB Output is correct
22 Correct 1074 ms 77396 KB Output is correct
23 Correct 358 ms 77200 KB Output is correct
24 Correct 681 ms 78212 KB Output is correct
25 Correct 985 ms 78564 KB Output is correct
26 Correct 904 ms 78648 KB Output is correct
27 Correct 853 ms 78160 KB Output is correct
28 Runtime error 212 ms 152148 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -