oj.uz

Submission #587326

# Submission time Handle Problem Language Result Execution time Memory
587326 2022-07-01T16:27:24 Z AlperenT Game (IOI13_game) C++17
63 / 100
 1544 ms 145412 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;

int n, m;

struct TwoDimSegTree{
    long long **tree;

    void set(int n = 0, int m = 0){
        tree = (long long**)malloc(n * 4 * sizeof(long long*));

        for(int i = 0; i < n * 4; i++) tree[i] = (long long*)malloc(m * 4 * sizeof(long long));
    }

    long long queryy(int vx, int vy, int tly, int try_, int ly, int ry){
        if(ly > ry) return 0;
        else if(ly == tly && ry == try_) return tree[vx][vy];
        else{
            int tmy = tly + (try_ - tly) / 2;

            return __gcd(queryy(vx, vy * 2, tly, tmy, ly, min(ry, tmy)), queryy(vx, vy * 2 + 1, tmy + 1, try_, max(ly, tmy + 1), ry));
        }
    }

    long long queryx(int vx, int tlx, int trx, int lx, int rx, int ly, int ry){
        if(lx > rx) return 0;
        else if(lx == tlx && rx == trx) return queryy(vx, 1, 0, m - 1, ly, ry);
        else{
            int tmx = tlx + (trx - tlx) / 2;

            return __gcd(queryx(vx * 2, tlx, tmx, lx, min(rx, tmx), ly, ry), queryx(vx * 2 + 1, tmx + 1, trx, max(lx, tmx + 1), rx, ly, ry));
        }
    }

    void updatey(int vx, int lx, int rx, int vy, int ly, int ry, int posy, long long val){
        if(ly == ry){
            if(lx == rx) tree[vx][vy] = val;
            else tree[vx][vy] = __gcd(tree[vx * 2][vy], tree[vx * 2 + 1][vy]);
        }
        else{
            int my = ly + (ry - ly) / 2;

            if(posy <= my) updatey(vx, lx, rx, vy * 2, ly, my, posy, val);
            else updatey(vx, lx, rx, vy * 2 + 1, my + 1, ry, posy, val);

            tree[vx][vy] = __gcd(tree[vx][vy * 2], tree[vx][vy * 2 + 1]);
        }
    }

    void updatex(int vx, int lx, int rx, int posx, int posy, long long val){
        if(lx != rx){
            int mx = lx + (rx - lx) / 2;

            if(posx <= mx) updatex(vx * 2, lx, mx, posx, posy, val);
            else updatex(vx * 2 + 1, mx + 1, rx, posx, posy, val);
        }

        updatey(vx, lx, rx, 1, 0, m - 1, posy, val);
    }
};

TwoDimSegTree sgt;

void init(int R, int C){
    n = R, m = C;

    sgt.set(n, m);
}

void update(int P, int Q, long long K) {
    sgt.updatex(1, 0, n - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return sgt.queryx(1, 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 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 2 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 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 340 KB Output is correct
4 Correct 618 ms 39032 KB Output is correct
5 Correct 469 ms 39452 KB Output is correct
6 Correct 540 ms 39756 KB Output is correct
7 Correct 536 ms 39492 KB Output is correct
8 Correct 438 ms 37920 KB Output is correct
9 Correct 531 ms 39596 KB Output is correct
10 Correct 472 ms 39116 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 0 ms 212 KB Output is correct
2 Correct 2 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 767 ms 51504 KB Output is correct
13 Correct 1097 ms 43468 KB Output is correct
14 Correct 603 ms 35852 KB Output is correct
15 Correct 1318 ms 101516 KB Output is correct
16 Correct 220 ms 144492 KB Output is correct
17 Correct 1071 ms 126836 KB Output is correct
18 Correct 1387 ms 144940 KB Output is correct
19 Correct 1459 ms 144968 KB Output is correct
20 Correct 1279 ms 144228 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 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 580 ms 39208 KB Output is correct
13 Correct 428 ms 39532 KB Output is correct
14 Correct 528 ms 39792 KB Output is correct
15 Correct 530 ms 39584 KB Output is correct
16 Correct 452 ms 38008 KB Output is correct
17 Correct 538 ms 39500 KB Output is correct
18 Correct 492 ms 39080 KB Output is correct
19 Correct 779 ms 51388 KB Output is correct
20 Correct 1104 ms 43600 KB Output is correct
21 Correct 609 ms 35988 KB Output is correct
22 Correct 1313 ms 101492 KB Output is correct
23 Correct 231 ms 144508 KB Output is correct
24 Correct 1123 ms 126716 KB Output is correct
25 Correct 1430 ms 144948 KB Output is correct
26 Correct 1544 ms 145180 KB Output is correct
27 Correct 1432 ms 144516 KB Output is correct
28 Runtime error 2 ms 468 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 1 ms 212 KB Output is correct
2 Correct 1 ms 1564 KB Output is correct
3 Correct 2 ms 1492 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2 ms 1492 KB Output is correct
6 Correct 2 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1524 KB Output is correct
11 Correct 2 ms 1492 KB Output is correct
12 Correct 733 ms 39464 KB Output is correct
13 Correct 425 ms 39900 KB Output is correct
14 Correct 522 ms 40168 KB Output is correct
15 Correct 637 ms 39920 KB Output is correct
16 Correct 466 ms 38360 KB Output is correct
17 Correct 526 ms 40000 KB Output is correct
18 Correct 485 ms 39500 KB Output is correct
19 Correct 959 ms 51784 KB Output is correct
20 Correct 1084 ms 43908 KB Output is correct
21 Correct 576 ms 36348 KB Output is correct
22 Correct 1293 ms 101960 KB Output is correct
23 Correct 225 ms 144904 KB Output is correct
24 Correct 1051 ms 127180 KB Output is correct
25 Correct 1246 ms 145412 KB Output is correct
26 Correct 1238 ms 145396 KB Output is correct
27 Correct 1136 ms 144736 KB Output is correct
28 Runtime error 1 ms 340 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -