oj.uz

Submission #551082

# Submission time Handle Problem Language Result Execution time Memory
551082 2022-04-19T19:52:51 Z tatyam Game (IOI13_game) C++17
63 / 100
 2068 ms 256000 KB 
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;

u32 R, C;
struct DynamicSegTree2D{
    unordered_map<u32, unordered_map<u32, u64>> seg;
    void set(u32 i, u32 j, u64 x){
        seg[i][j] = x;
        for(int jj = j; jj >>= 1; ) seg[i][jj] = gcd(seg[i][jj << 1], seg[i][jj << 1 | 1]);
        for(int ii = i; ii >>= 1; ) seg[ii][j] = gcd(seg[ii << 1][j], seg[ii << 1 | 1][j]);
        for(int ii = i; ii >>= 1; ){
            auto& s = seg[ii];
            for(int jj = j; jj >>= 1; ) s[jj] = gcd(s[jj << 1], s[jj << 1 | 1]);
        }
    }
    u64 get(const unordered_map<u32, u64>& s, u32 j) const {
        auto p = s.find(j);
        if(p == s.end()) return 0;
        return p->second;
    }
    u64 get(u32 i, u32 l, u32 r) const {
        auto p = seg.find(i);
        if(p == seg.end()) return 0;
        auto& s = p->second;
        u64 ans = 0;
        while(l < r){
            if(l & 1) ans = gcd(ans, get(s, l++));
            if(r & 1) ans = gcd(ans, get(s, --r));
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
    u64 get(u32 l, u32 r, u32 y_l, u32 y_r) const {
        u64 ans = 0;
        while(l < r){
            if(l & 1) ans = gcd(ans, get(l++, y_l, y_r));
            if(r & 1) ans = gcd(ans, get(--r, y_l, y_r));
            l >>= 1;
            r >>= 1;
        }
        return ans;
    }
} seg;

extern "C" {

void init(int R_, int C_){
    R = 1;
    C = 1;
    while(R < R_) R <<= 1;
    while(C < C_) C <<= 1;
}

void update(int P, int Q, long long K){
    P += R;
    Q += C;
    seg.set(P, Q, K);
}

long long calculate(int P, int Q, int U, int V){
    P += R;
    Q += C;
    U += R + 1;
    V += C + 1;
    return seg.get(P, U, Q, V);
}

}

Compilation message

game.cpp: In function 'void init(int, int)':
game.cpp:53:13: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   53 |     while(R < R_) R <<= 1;
      |           ~~^~~~
game.cpp:54:13: warning: comparison of integer expressions of different signedness: 'u32' {aka 'unsigned int'} and 'int' [-Wsign-compare]
   54 |     while(C < C_) C <<= 1;
      |           ~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 774 ms 30736 KB Output is correct
5 Correct 562 ms 30604 KB Output is correct
6 Correct 726 ms 29916 KB Output is correct
7 Correct 786 ms 29532 KB Output is correct
8 Correct 469 ms 19424 KB Output is correct
9 Correct 803 ms 29272 KB Output is correct
10 Correct 739 ms 28776 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 416 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1100 ms 35476 KB Output is correct
13 Correct 1404 ms 16972 KB Output is correct
14 Correct 562 ms 5792 KB Output is correct
15 Correct 1791 ms 23848 KB Output is correct
16 Correct 570 ms 47436 KB Output is correct
17 Correct 1193 ms 31176 KB Output is correct
18 Correct 1895 ms 48904 KB Output is correct
19 Correct 1702 ms 49012 KB Output is correct
20 Correct 1581 ms 48508 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 556 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 552 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 727 ms 30896 KB Output is correct
13 Correct 547 ms 30568 KB Output is correct
14 Correct 728 ms 29908 KB Output is correct
15 Correct 789 ms 29412 KB Output is correct
16 Correct 473 ms 19456 KB Output is correct
17 Correct 810 ms 29208 KB Output is correct
18 Correct 701 ms 28752 KB Output is correct
19 Correct 1072 ms 35388 KB Output is correct
20 Correct 1359 ms 16740 KB Output is correct
21 Correct 560 ms 5836 KB Output is correct
22 Correct 1715 ms 23876 KB Output is correct
23 Correct 581 ms 47384 KB Output is correct
24 Correct 1188 ms 31208 KB Output is correct
25 Correct 2068 ms 48812 KB Output is correct
26 Correct 1784 ms 49032 KB Output is correct
27 Correct 1641 ms 48472 KB Output is correct
28 Runtime error 1278 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 788 ms 30980 KB Output is correct
13 Correct 575 ms 30668 KB Output is correct
14 Correct 757 ms 30060 KB Output is correct
15 Correct 833 ms 29364 KB Output is correct
16 Correct 481 ms 19680 KB Output is correct
17 Correct 839 ms 29236 KB Output is correct
18 Correct 738 ms 28912 KB Output is correct
19 Correct 1126 ms 35540 KB Output is correct
20 Correct 1386 ms 17040 KB Output is correct
21 Correct 541 ms 5808 KB Output is correct
22 Correct 1752 ms 23916 KB Output is correct
23 Correct 583 ms 47432 KB Output is correct
24 Correct 1243 ms 31368 KB Output is correct
25 Correct 1982 ms 48692 KB Output is correct
26 Correct 1752 ms 49180 KB Output is correct
27 Correct 1687 ms 48460 KB Output is correct
28 Runtime error 1177 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -