oj.uz

Submission #1075895

# Submission time Handle Problem Language Result Execution time Memory
1075895 2024-08-26T09:40:31 Z mc061 Game (IOI13_game) C++17
63 / 100
 1198 ms 146256 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 18 ms 72028 KB Output is correct
2 Correct 19 ms 72028 KB Output is correct
3 Correct 19 ms 72028 KB Output is correct
4 Correct 17 ms 72020 KB Output is correct
5 Correct 16 ms 72184 KB Output is correct
6 Correct 19 ms 72128 KB Output is correct
7 Correct 18 ms 72028 KB Output is correct
8 Correct 17 ms 72044 KB Output is correct
9 Correct 23 ms 72024 KB Output is correct
10 Correct 20 ms 72028 KB Output is correct
11 Correct 21 ms 72028 KB Output is correct
12 Correct 17 ms 72144 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 72016 KB Output is correct
2 Correct 18 ms 72128 KB Output is correct
3 Correct 17 ms 72024 KB Output is correct
4 Correct 439 ms 76128 KB Output is correct
5 Correct 350 ms 76368 KB Output is correct
6 Correct 481 ms 73312 KB Output is correct
7 Correct 461 ms 72996 KB Output is correct
8 Correct 341 ms 73732 KB Output is correct
9 Correct 454 ms 73052 KB Output is correct
10 Correct 447 ms 72528 KB Output is correct
11 Correct 18 ms 72024 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 72276 KB Output is correct
2 Correct 19 ms 72196 KB Output is correct
3 Correct 17 ms 72028 KB Output is correct
4 Correct 17 ms 72024 KB Output is correct
5 Correct 18 ms 72028 KB Output is correct
6 Correct 20 ms 72028 KB Output is correct
7 Correct 18 ms 72028 KB Output is correct
8 Correct 18 ms 72024 KB Output is correct
9 Correct 19 ms 72028 KB Output is correct
10 Correct 19 ms 72028 KB Output is correct
11 Correct 21 ms 72024 KB Output is correct
12 Correct 801 ms 76236 KB Output is correct
13 Correct 1071 ms 72788 KB Output is correct
14 Correct 368 ms 72760 KB Output is correct
15 Correct 1149 ms 72832 KB Output is correct
16 Correct 378 ms 72788 KB Output is correct
17 Correct 771 ms 73324 KB Output is correct
18 Correct 1090 ms 73164 KB Output is correct
19 Correct 1065 ms 73244 KB Output is correct
20 Correct 981 ms 72728 KB Output is correct
21 Correct 23 ms 72028 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 72028 KB Output is correct
2 Correct 31 ms 72216 KB Output is correct
3 Correct 20 ms 72028 KB Output is correct
4 Correct 22 ms 72028 KB Output is correct
5 Correct 25 ms 72020 KB Output is correct
6 Correct 27 ms 72028 KB Output is correct
7 Correct 20 ms 72044 KB Output is correct
8 Correct 30 ms 72088 KB Output is correct
9 Correct 18 ms 72028 KB Output is correct
10 Correct 20 ms 72028 KB Output is correct
11 Correct 28 ms 72020 KB Output is correct
12 Correct 515 ms 76032 KB Output is correct
13 Correct 416 ms 76540 KB Output is correct
14 Correct 537 ms 73276 KB Output is correct
15 Correct 553 ms 72928 KB Output is correct
16 Correct 359 ms 73696 KB Output is correct
17 Correct 563 ms 73044 KB Output is correct
18 Correct 522 ms 72692 KB Output is correct
19 Correct 757 ms 76084 KB Output is correct
20 Correct 989 ms 72764 KB Output is correct
21 Correct 378 ms 72720 KB Output is correct
22 Correct 1184 ms 73084 KB Output is correct
23 Correct 386 ms 72752 KB Output is correct
24 Correct 818 ms 73500 KB Output is correct
25 Correct 1149 ms 73172 KB Output is correct
26 Correct 968 ms 73188 KB Output is correct
27 Correct 961 ms 72780 KB Output is correct
28 Runtime error 236 ms 146204 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 32 ms 72088 KB Output is correct
2 Correct 28 ms 72220 KB Output is correct
3 Correct 19 ms 72028 KB Output is correct
4 Correct 22 ms 72060 KB Output is correct
5 Correct 22 ms 72016 KB Output is correct
6 Correct 32 ms 72020 KB Output is correct
7 Correct 24 ms 72044 KB Output is correct
8 Correct 24 ms 72020 KB Output is correct
9 Correct 27 ms 72228 KB Output is correct
10 Correct 23 ms 72108 KB Output is correct
11 Correct 32 ms 72016 KB Output is correct
12 Correct 489 ms 76136 KB Output is correct
13 Correct 403 ms 76592 KB Output is correct
14 Correct 512 ms 73300 KB Output is correct
15 Correct 521 ms 72992 KB Output is correct
16 Correct 356 ms 73748 KB Output is correct
17 Correct 526 ms 73040 KB Output is correct
18 Correct 481 ms 72560 KB Output is correct
19 Correct 843 ms 76240 KB Output is correct
20 Correct 1064 ms 72884 KB Output is correct
21 Correct 398 ms 72556 KB Output is correct
22 Correct 1198 ms 72940 KB Output is correct
23 Correct 359 ms 72844 KB Output is correct
24 Correct 830 ms 73300 KB Output is correct
25 Correct 1096 ms 73072 KB Output is correct
26 Correct 1103 ms 73300 KB Output is correct
27 Correct 1022 ms 72768 KB Output is correct
28 Runtime error 261 ms 146256 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -