oj.uz

Submission #1075792

# Submission time Handle Problem Language Result Execution time Memory
1075792 2024-08-26T09:12:20 Z mc061 Game (IOI13_game) C++17
80 / 100
 2439 ms 256000 KB 
#pragma once

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

unordered_map<long long, int> big_idx;

const int SZ = 1e9+1;

struct segtree {
    struct smallnode {
        long long ans = 0;
        long long left = -1, right = -1;
    };
    struct bignode {
        long long left = -1, right = -1;
        vector<smallnode> smalls={smallnode()};
        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 = smalls.size();
                    smalls.push_back(smallnode());
                }
                update(idx, val, smalls[x].left, tl, m);
            }
            else {
                if (smalls[x].right == -1) {
                    smalls[x].right = smalls.size();
                    smalls.push_back(smallnode());
                }
                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);
        }
    };
    vector<bignode> bigs={bignode()};

    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);
            return;
        }
        int m = (tl + tr) >> 1;
        if (i <= m) {
            if (bigs[x].left == -1) {
                bigs[x].left = bigs.size();
                bigs.push_back(bignode());
            }
            update(i, j, val, bigs[x].left, tl, m);
        }
        else {
            if (bigs[x].right == -1) {
                bigs[x].right = bigs.size();
                bigs.push_back(bignode());
            }
            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));
        long long from_r = (bigs[x].right == -1 ? 0 : bigs[bigs[x].right].query(j, j));
        bigs[x].update(j, __gcd(from_l, from_r));
    }
    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);
        }
        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) {}
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 1 ms 344 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 824 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 2 ms 436 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 561 ms 45812 KB Output is correct
5 Correct 465 ms 46080 KB Output is correct
6 Correct 591 ms 43560 KB Output is correct
7 Correct 594 ms 43076 KB Output is correct
8 Correct 391 ms 27960 KB Output is correct
9 Correct 666 ms 42816 KB Output is correct
10 Correct 569 ms 42296 KB Output is correct
11 Correct 1 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 692 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 865 ms 23612 KB Output is correct
13 Correct 1010 ms 12876 KB Output is correct
14 Correct 410 ms 5968 KB Output is correct
15 Correct 1137 ms 17752 KB Output is correct
16 Correct 423 ms 28496 KB Output is correct
17 Correct 801 ms 21588 KB Output is correct
18 Correct 1232 ms 29808 KB Output is correct
19 Correct 1088 ms 29876 KB Output is correct
20 Correct 1043 ms 29460 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 4 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 432 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 587 ms 46060 KB Output is correct
13 Correct 574 ms 45864 KB Output is correct
14 Correct 629 ms 43512 KB Output is correct
15 Correct 554 ms 43068 KB Output is correct
16 Correct 391 ms 28084 KB Output is correct
17 Correct 618 ms 42900 KB Output is correct
18 Correct 540 ms 42304 KB Output is correct
19 Correct 836 ms 23692 KB Output is correct
20 Correct 989 ms 12928 KB Output is correct
21 Correct 368 ms 5968 KB Output is correct
22 Correct 1139 ms 17696 KB Output is correct
23 Correct 402 ms 28500 KB Output is correct
24 Correct 827 ms 21524 KB Output is correct
25 Correct 1178 ms 30004 KB Output is correct
26 Correct 1109 ms 30036 KB Output is correct
27 Correct 1047 ms 29392 KB Output is correct
28 Correct 646 ms 226944 KB Output is correct
29 Correct 1269 ms 248148 KB Output is correct
30 Correct 2439 ms 181656 KB Output is correct
31 Correct 2439 ms 147172 KB Output is correct
32 Correct 349 ms 10612 KB Output is correct
33 Correct 458 ms 13908 KB Output is correct
34 Correct 772 ms 242252 KB Output is correct
35 Correct 952 ms 129308 KB Output is correct
36 Correct 1782 ms 246216 KB Output is correct
37 Correct 1461 ms 246432 KB Output is correct
38 Correct 1570 ms 245800 KB Output is correct
39 Correct 1257 ms 192000 KB Output is correct
40 Correct 1 ms 432 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 436 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 649 ms 45820 KB Output is correct
13 Correct 544 ms 46072 KB Output is correct
14 Correct 619 ms 43648 KB Output is correct
15 Correct 651 ms 42840 KB Output is correct
16 Correct 387 ms 27968 KB Output is correct
17 Correct 579 ms 42844 KB Output is correct
18 Correct 538 ms 42300 KB Output is correct
19 Correct 825 ms 23528 KB Output is correct
20 Correct 997 ms 12884 KB Output is correct
21 Correct 398 ms 5976 KB Output is correct
22 Correct 1126 ms 17744 KB Output is correct
23 Correct 399 ms 28504 KB Output is correct
24 Correct 817 ms 21584 KB Output is correct
25 Correct 1148 ms 29776 KB Output is correct
26 Correct 1096 ms 29924 KB Output is correct
27 Correct 1014 ms 29356 KB Output is correct
28 Correct 568 ms 226688 KB Output is correct
29 Correct 1252 ms 248300 KB Output is correct
30 Correct 2369 ms 181512 KB Output is correct
31 Correct 2407 ms 147048 KB Output is correct
32 Correct 364 ms 10500 KB Output is correct
33 Correct 474 ms 14104 KB Output is correct
34 Correct 727 ms 242480 KB Output is correct
35 Correct 932 ms 129328 KB Output is correct
36 Correct 1746 ms 246204 KB Output is correct
37 Correct 1323 ms 246404 KB Output is correct
38 Correct 1271 ms 245784 KB Output is correct
39 Runtime error 426 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -