oj.uz

Submission #587459

# Submission time Handle Problem Language Result Execution time Memory
587459 2022-07-01T22:38:03 Z AlperenT Game (IOI13_game) C++17
63 / 100
 1524 ms 256000 KB 
#include <bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
int N, M;

struct NodeY{
    long long val = 0;

    NodeY *lptr_y = nullptr, *rptr_y = nullptr;
};

struct NodeX{
    NodeX *lptr_x = nullptr, *rptr_x = nullptr;
    NodeY *ptr_y = nullptr;
};
 
struct TwoDimSegTree{
    NodeX *root;

    long long query_y(NodeY *v, int tl, int tr, int ly, int ry){
        if(!v || ly > ry) return 0;
        else if(tl == ly && tr == ry) return v->val;
        else{
            int tm = tl + (tr - tl) / 2;

            return __gcd(query_y(v->lptr_y, tl, tm, ly, min(ry, tm)), query_y(v->rptr_y, tm + 1, tr, max(ly, tm + 1), ry));
        }
    }

    long long query_x(NodeX *v, int tl, int tr, int lx, int rx, int ly, int ry){
        if(!v || lx > rx) return 0;
        else if(tl == lx && tr == rx) return query_y(v->ptr_y, 0, M - 1, ly, ry);
        else{
            int tm = tl + (tr - tl) / 2;

            return __gcd(query_x(v->lptr_x, tl, tm, lx, min(tm, rx), ly, ry), query_x(v->rptr_x, tm + 1, tr, max(lx, tm + 1), rx, ly, ry));
        }
    }

    void update_y(NodeY *&v, int l, int r, int pos, long long val){
        if(!v) v = new NodeY();

        if(l == r) v->val = val;
        else{
            int m = l + (r - l) / 2;

            if(pos <= m) update_y(v->lptr_y, l, m, pos, val);
            else update_y(v->rptr_y, m + 1, r, pos, val);

            v->val = __gcd(v->lptr_y ? v->lptr_y->val : 0, v->rptr_y ? v->rptr_y->val : 0);
        }
    }

    void update_x(NodeX *&v, int l, int r, int posx, int posy, long long val){
        if(!v) v = new NodeX();

        if(l == r) update_y(v->ptr_y, 0, M - 1, posy, val);
        else{
            int m = l + (r - l) / 2;

            if(posx <= m) update_x(v->lptr_x, l, m, posx, posy, val);
            else update_x(v->rptr_x, m + 1, r, posx, posy, val);

            val = __gcd(v->lptr_x ? query_y(v->lptr_x->ptr_y, 0, M - 1, posy, posy) : 0, v->rptr_x ? query_y(v->rptr_x->ptr_y, 0, M - 1, posy, posy) : 0);

            update_y(v->ptr_y, 0, M - 1, posy, val);
        }
    }
};
 
TwoDimSegTree sgt;
 
void init(int R, int C){
    N = R, M = C;
}
 
void update(int P, int Q, long long K) {
    sgt.update_x(sgt.root, 0, N - 1, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
    return sgt.query_x(sgt.root, 0, N - 1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 481 ms 12544 KB Output is correct
5 Correct 322 ms 12896 KB Output is correct
6 Correct 426 ms 9804 KB Output is correct
7 Correct 488 ms 9564 KB Output is correct
8 Correct 338 ms 6572 KB Output is correct
9 Correct 450 ms 9760 KB Output is correct
10 Correct 411 ms 9224 KB Output is correct
11 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 745 ms 15816 KB Output is correct
13 Correct 1181 ms 6120 KB Output is correct
14 Correct 256 ms 928 KB Output is correct
15 Correct 1365 ms 8792 KB Output is correct
16 Correct 225 ms 18220 KB Output is correct
17 Correct 679 ms 11412 KB Output is correct
18 Correct 1172 ms 18576 KB Output is correct
19 Correct 1148 ms 18748 KB Output is correct
20 Correct 936 ms 18036 KB Output is correct
21 Correct 0 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 497 ms 12616 KB Output is correct
13 Correct 346 ms 12920 KB Output is correct
14 Correct 401 ms 9924 KB Output is correct
15 Correct 484 ms 9564 KB Output is correct
16 Correct 313 ms 6604 KB Output is correct
17 Correct 486 ms 9628 KB Output is correct
18 Correct 428 ms 9188 KB Output is correct
19 Correct 763 ms 15792 KB Output is correct
20 Correct 1140 ms 6136 KB Output is correct
21 Correct 265 ms 848 KB Output is correct
22 Correct 1413 ms 8700 KB Output is correct
23 Correct 205 ms 18156 KB Output is correct
24 Correct 669 ms 11488 KB Output is correct
25 Correct 1208 ms 18552 KB Output is correct
26 Correct 1054 ms 18840 KB Output is correct
27 Correct 946 ms 18148 KB Output is correct
28 Correct 829 ms 251488 KB Output is correct
29 Runtime error 1524 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 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 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 481 ms 12592 KB Output is correct
13 Correct 335 ms 12940 KB Output is correct
14 Correct 446 ms 9744 KB Output is correct
15 Correct 448 ms 9568 KB Output is correct
16 Correct 312 ms 6616 KB Output is correct
17 Correct 445 ms 9680 KB Output is correct
18 Correct 387 ms 9280 KB Output is correct
19 Correct 793 ms 15796 KB Output is correct
20 Correct 1171 ms 6300 KB Output is correct
21 Correct 259 ms 892 KB Output is correct
22 Correct 1408 ms 8656 KB Output is correct
23 Correct 188 ms 18252 KB Output is correct
24 Correct 741 ms 11416 KB Output is correct
25 Correct 1169 ms 18444 KB Output is correct
26 Correct 1048 ms 18776 KB Output is correct
27 Correct 970 ms 18088 KB Output is correct
28 Correct 883 ms 251660 KB Output is correct
29 Runtime error 1513 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -