oj.uz

Submission #1075954

# Submission time Handle Problem Language Result Execution time Memory
1075954 2024-08-26T10:01:18 Z mc061 Game (IOI13_game) C++17
63 / 100
 1130 ms 256000 KB 
#pragma once

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

const int SZ = 1e9+1;

const int SMALL_SZ = 1.5e7;

struct smallnode {
    long long ans;
    int left, right;
    smallnode() {
        ans = 0, left = -1, right = -1;
    }
};
vector<smallnode> smalls;
int nxt_free = 0;
int create() {
    smalls.push_back(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);
    }
};
vector<bignode> bigs;
int nxt_free_big = 0;
int create_big() {
    bigs.push_back(bignode());
    bigs[nxt_free_big].root = create();
    return nxt_free_big++;
}

void update_seg(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_seg(i, j, val, bigs[x].left, tl, m);
    }
    else {
        if (bigs[x].right == -1) {
            bigs[x].right = create_big();
        }
        update_seg(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;

void init(int R, int C) {
    create_big();
}
void update(int P, int Q, long long K) {
    update_seg(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
    // cerr << smalls.size() << " " << bigs.size() << endl;
    return 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 728 KB Output is correct
3 Correct 2 ms 728 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 728 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 728 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 473 ms 37540 KB Output is correct
5 Correct 351 ms 37796 KB Output is correct
6 Correct 475 ms 35324 KB Output is correct
7 Correct 488 ms 34792 KB Output is correct
8 Correct 328 ms 19112 KB Output is correct
9 Correct 475 ms 34472 KB Output is correct
10 Correct 429 ms 33700 KB Output is correct
11 Correct 1 ms 348 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 680 KB Output is correct
3 Correct 2 ms 728 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 728 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 724 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 755 ms 12432 KB Output is correct
13 Correct 947 ms 5168 KB Output is correct
14 Correct 347 ms 1120 KB Output is correct
15 Correct 1079 ms 10172 KB Output is correct
16 Correct 358 ms 18092 KB Output is correct
17 Correct 700 ms 9388 KB Output is correct
18 Correct 990 ms 18044 KB Output is correct
19 Correct 924 ms 17840 KB Output is correct
20 Correct 889 ms 17708 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 728 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 720 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 728 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 482 ms 36700 KB Output is correct
13 Correct 382 ms 36812 KB Output is correct
14 Correct 461 ms 35932 KB Output is correct
15 Correct 485 ms 34472 KB Output is correct
16 Correct 338 ms 18500 KB Output is correct
17 Correct 504 ms 34984 KB Output is correct
18 Correct 494 ms 33448 KB Output is correct
19 Correct 728 ms 11696 KB Output is correct
20 Correct 948 ms 5092 KB Output is correct
21 Correct 397 ms 1224 KB Output is correct
22 Correct 1096 ms 10220 KB Output is correct
23 Correct 345 ms 17224 KB Output is correct
24 Correct 704 ms 10420 KB Output is correct
25 Correct 1039 ms 17584 KB Output is correct
26 Correct 936 ms 18340 KB Output is correct
27 Correct 867 ms 19120 KB Output is correct
28 Correct 487 ms 134544 KB Output is correct
29 Runtime error 1130 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 728 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 728 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 728 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 468 ms 37036 KB Output is correct
13 Correct 385 ms 38200 KB Output is correct
14 Correct 529 ms 34512 KB Output is correct
15 Correct 484 ms 33700 KB Output is correct
16 Correct 334 ms 18280 KB Output is correct
17 Correct 481 ms 35472 KB Output is correct
18 Correct 433 ms 34728 KB Output is correct
19 Correct 786 ms 11696 KB Output is correct
20 Correct 963 ms 6344 KB Output is correct
21 Correct 346 ms 1204 KB Output is correct
22 Correct 1054 ms 8888 KB Output is correct
23 Correct 335 ms 18196 KB Output is correct
24 Correct 712 ms 11188 KB Output is correct
25 Correct 1020 ms 18096 KB Output is correct
26 Correct 953 ms 18604 KB Output is correct
27 Correct 869 ms 17580 KB Output is correct
28 Correct 520 ms 135172 KB Output is correct
29 Runtime error 1064 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -