oj.uz

Submission #1075805

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

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

const int SZ = 1e9+1;

struct segtree {
    struct smallnode {
        long long ans = 0;
        int left = -1, right = -1;
    };
    struct bignode {
        int 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 348 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 440 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 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Correct 0 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 641 ms 33208 KB Output is correct
5 Correct 503 ms 33464 KB Output is correct
6 Correct 581 ms 31108 KB Output is correct
7 Correct 612 ms 30080 KB Output is correct
8 Correct 408 ms 20100 KB Output is correct
9 Correct 606 ms 29628 KB Output is correct
10 Correct 546 ms 29464 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 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 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 825 ms 17800 KB Output is correct
13 Correct 987 ms 9832 KB Output is correct
14 Correct 364 ms 4948 KB Output is correct
15 Correct 1130 ms 13136 KB Output is correct
16 Correct 414 ms 20816 KB Output is correct
17 Correct 731 ms 15700 KB Output is correct
18 Correct 1124 ms 21900 KB Output is correct
19 Correct 998 ms 21756 KB Output is correct
20 Correct 947 ms 21076 KB Output is correct
21 Correct 1 ms 432 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 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 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 684 KB Output is correct
7 Correct 1 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 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 560 ms 32692 KB Output is correct
13 Correct 476 ms 32960 KB Output is correct
14 Correct 542 ms 30240 KB Output is correct
15 Correct 662 ms 29512 KB Output is correct
16 Correct 393 ms 20144 KB Output is correct
17 Correct 550 ms 29816 KB Output is correct
18 Correct 511 ms 29652 KB Output is correct
19 Correct 818 ms 18004 KB Output is correct
20 Correct 1065 ms 9872 KB Output is correct
21 Correct 363 ms 5172 KB Output is correct
22 Correct 1172 ms 13172 KB Output is correct
23 Correct 406 ms 20816 KB Output is correct
24 Correct 785 ms 15700 KB Output is correct
25 Correct 1204 ms 21616 KB Output is correct
26 Correct 1220 ms 21740 KB Output is correct
27 Correct 1084 ms 21184 KB Output is correct
28 Correct 582 ms 153888 KB Output is correct
29 Correct 1265 ms 169040 KB Output is correct
30 Correct 2509 ms 122444 KB Output is correct
31 Correct 2563 ms 100708 KB Output is correct
32 Correct 357 ms 9716 KB Output is correct
33 Correct 472 ms 12068 KB Output is correct
34 Correct 726 ms 165100 KB Output is correct
35 Correct 872 ms 89584 KB Output is correct
36 Correct 1568 ms 168364 KB Output is correct
37 Correct 1420 ms 168516 KB Output is correct
38 Correct 1327 ms 168172 KB Output is correct
39 Correct 1139 ms 132088 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 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 604 KB Output is correct
6 Correct 2 ms 692 KB Output is correct
7 Correct 1 ms 348 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 436 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 593 ms 33420 KB Output is correct
13 Correct 502 ms 33432 KB Output is correct
14 Correct 676 ms 30996 KB Output is correct
15 Correct 613 ms 30192 KB Output is correct
16 Correct 452 ms 20584 KB Output is correct
17 Correct 578 ms 30528 KB Output is correct
18 Correct 541 ms 30296 KB Output is correct
19 Correct 946 ms 18380 KB Output is correct
20 Correct 1034 ms 10336 KB Output is correct
21 Correct 402 ms 5688 KB Output is correct
22 Correct 1137 ms 13692 KB Output is correct
23 Correct 382 ms 21284 KB Output is correct
24 Correct 709 ms 16520 KB Output is correct
25 Correct 999 ms 22356 KB Output is correct
26 Correct 990 ms 22500 KB Output is correct
27 Correct 896 ms 21824 KB Output is correct
28 Correct 486 ms 155232 KB Output is correct
29 Correct 1010 ms 170524 KB Output is correct
30 Correct 2261 ms 123568 KB Output is correct
31 Correct 2193 ms 101000 KB Output is correct
32 Correct 304 ms 9552 KB Output is correct
33 Correct 431 ms 12012 KB Output is correct
34 Correct 632 ms 163996 KB Output is correct
35 Correct 739 ms 88508 KB Output is correct
36 Correct 1460 ms 167148 KB Output is correct
37 Correct 1249 ms 167216 KB Output is correct
38 Correct 1314 ms 166748 KB Output is correct
39 Runtime error 705 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -