oj.uz

Submission #1075906

# Submission time Handle Problem Language Result Execution time Memory
1075906 2024-08-26T09:43:04 Z mc061 Game (IOI13_game) C++17
63 / 100
 1071 ms 160852 KB 
#pragma once

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

const int SZ = 1e9+1;

const int SMALL_SZ = 5e6;

struct smallnode {
    long long ans;
    int left, right;
    smallnode() {
        ans = 0, left = -1, right = -1;
    }
};
smallnode smalls[SMALL_SZ];
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<<16];
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 20 ms 79452 KB Output is correct
2 Correct 20 ms 79384 KB Output is correct
3 Correct 21 ms 79452 KB Output is correct
4 Correct 19 ms 79260 KB Output is correct
5 Correct 19 ms 79440 KB Output is correct
6 Correct 22 ms 79452 KB Output is correct
7 Correct 17 ms 79264 KB Output is correct
8 Correct 22 ms 79328 KB Output is correct
9 Correct 18 ms 79452 KB Output is correct
10 Correct 17 ms 79320 KB Output is correct
11 Correct 19 ms 79448 KB Output is correct
12 Correct 20 ms 79452 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 79448 KB Output is correct
2 Correct 18 ms 79452 KB Output is correct
3 Correct 20 ms 79452 KB Output is correct
4 Correct 442 ms 83288 KB Output is correct
5 Correct 392 ms 83792 KB Output is correct
6 Correct 471 ms 80468 KB Output is correct
7 Correct 534 ms 80228 KB Output is correct
8 Correct 356 ms 80980 KB Output is correct
9 Correct 469 ms 80212 KB Output is correct
10 Correct 435 ms 79956 KB Output is correct
11 Correct 21 ms 79348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 79420 KB Output is correct
2 Correct 28 ms 79448 KB Output is correct
3 Correct 23 ms 79324 KB Output is correct
4 Correct 22 ms 79304 KB Output is correct
5 Correct 20 ms 79460 KB Output is correct
6 Correct 21 ms 79448 KB Output is correct
7 Correct 20 ms 79452 KB Output is correct
8 Correct 20 ms 79364 KB Output is correct
9 Correct 22 ms 79448 KB Output is correct
10 Correct 22 ms 79452 KB Output is correct
11 Correct 23 ms 79444 KB Output is correct
12 Correct 726 ms 83300 KB Output is correct
13 Correct 946 ms 79980 KB Output is correct
14 Correct 353 ms 79952 KB Output is correct
15 Correct 1066 ms 79952 KB Output is correct
16 Correct 360 ms 80208 KB Output is correct
17 Correct 714 ms 80768 KB Output is correct
18 Correct 1012 ms 80596 KB Output is correct
19 Correct 927 ms 80592 KB Output is correct
20 Correct 896 ms 79956 KB Output is correct
21 Correct 21 ms 79452 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 79448 KB Output is correct
2 Correct 22 ms 79452 KB Output is correct
3 Correct 25 ms 79288 KB Output is correct
4 Correct 24 ms 79452 KB Output is correct
5 Correct 29 ms 79284 KB Output is correct
6 Correct 39 ms 79452 KB Output is correct
7 Correct 27 ms 79428 KB Output is correct
8 Correct 27 ms 79452 KB Output is correct
9 Correct 26 ms 79256 KB Output is correct
10 Correct 27 ms 79376 KB Output is correct
11 Correct 27 ms 79452 KB Output is correct
12 Correct 523 ms 83464 KB Output is correct
13 Correct 397 ms 83632 KB Output is correct
14 Correct 508 ms 80348 KB Output is correct
15 Correct 524 ms 80480 KB Output is correct
16 Correct 389 ms 80912 KB Output is correct
17 Correct 465 ms 80260 KB Output is correct
18 Correct 450 ms 79956 KB Output is correct
19 Correct 752 ms 83384 KB Output is correct
20 Correct 983 ms 79956 KB Output is correct
21 Correct 356 ms 79952 KB Output is correct
22 Correct 1059 ms 79988 KB Output is correct
23 Correct 405 ms 79964 KB Output is correct
24 Correct 706 ms 80884 KB Output is correct
25 Correct 1018 ms 80468 KB Output is correct
26 Correct 914 ms 80580 KB Output is correct
27 Correct 871 ms 79952 KB Output is correct
28 Runtime error 208 ms 160852 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 21 ms 79452 KB Output is correct
2 Correct 23 ms 79296 KB Output is correct
3 Correct 23 ms 79452 KB Output is correct
4 Correct 23 ms 79356 KB Output is correct
5 Correct 22 ms 79452 KB Output is correct
6 Correct 24 ms 79452 KB Output is correct
7 Correct 23 ms 79448 KB Output is correct
8 Correct 21 ms 79252 KB Output is correct
9 Correct 24 ms 79452 KB Output is correct
10 Correct 23 ms 79448 KB Output is correct
11 Correct 24 ms 79452 KB Output is correct
12 Correct 458 ms 83484 KB Output is correct
13 Correct 374 ms 83796 KB Output is correct
14 Correct 467 ms 80464 KB Output is correct
15 Correct 525 ms 80208 KB Output is correct
16 Correct 349 ms 80980 KB Output is correct
17 Correct 502 ms 80208 KB Output is correct
18 Correct 445 ms 79952 KB Output is correct
19 Correct 788 ms 83536 KB Output is correct
20 Correct 939 ms 79976 KB Output is correct
21 Correct 363 ms 79988 KB Output is correct
22 Correct 1071 ms 80204 KB Output is correct
23 Correct 346 ms 80212 KB Output is correct
24 Correct 705 ms 80724 KB Output is correct
25 Correct 988 ms 80300 KB Output is correct
26 Correct 918 ms 80468 KB Output is correct
27 Correct 908 ms 79952 KB Output is correct
28 Runtime error 209 ms 160848 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -