oj.uz

Submission #1091139

# Submission time Handle Problem Language Result Execution time Memory
1091139 2024-09-19T22:52:28 Z vjudge1 Game (IOI13_game) C++17
63 / 100
 999 ms 131504 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long n, m;
long long tree[4*2005][4*2005];
long long tree2[4*10][4*100005];

long long nzd(long long a, long long b) {
    if (b==0) return a;
    return nzd(b, a%b);
}

long long query_y(int kx, int ky, int left, int right, int levo_kol, int desno_kol) {
    if (m<=2000) {
        if (left>=levo_kol && right<=desno_kol)
            return tree[kx][ky];
        else if (left>desno_kol || right<levo_kol)
            return 0;
        int mid=(left+right)/2;
        long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
        long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
        return nzd(r1, r2);
    }
    else {
        if (left>=levo_kol && right<=desno_kol)
            return tree2[kx][ky];
        else if (left>desno_kol || right<levo_kol)
            return 0;
        int mid=(left+right)/2;
        long long r1=query_y(kx, 2*ky, left, mid, levo_kol, desno_kol);
        long long r2=query_y(kx, 2*ky+1, mid+1, right, levo_kol, desno_kol);
        return nzd(r1, r2);
    }
}

long long query_x(int k, int left, int right, int gore_red, int dole_red, int levo_kol, int desno_kol) {
    if (left>=gore_red && right<=dole_red)
        return query_y(k, 1, 0, m-1, levo_kol, desno_kol);
    else if (left>dole_red || right<gore_red)
        return 0;
    int mid=(left+right)/2;
    long long r1=query_x(2*k, left, mid, gore_red, dole_red, levo_kol, desno_kol);
    long long r2=query_x(2*k+1, mid+1, right, gore_red, dole_red, levo_kol, desno_kol);
    return nzd(r1, r2);
}

void update_y(int kx, int left_x, int right_x, int ky, int left_y, int right_y, int row, int col, long long val) {
    if (m<=2000) {
        if (left_y==right_y) {
            if (left_x==right_x)
                tree[kx][ky]=val;
            else
                tree[kx][ky]=nzd(tree[2*kx][ky], tree[2*kx+1][ky]);
        }
        else {
            int mid=(left_y+right_y)/2;
            if (col>mid)
                update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
            else
                update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
            tree[kx][ky]=nzd(tree[kx][2*ky], tree[kx][2*ky+1]);
        }
    }
    else {
        if (left_y==right_y) {
            if (left_x==right_x)
                tree2[kx][ky]=val;
            else
                tree2[kx][ky]=nzd(tree2[2*kx][ky], tree2[2*kx+1][ky]);
        }
        else {
            int mid=(left_y+right_y)/2;
            if (col>mid)
                update_y(kx, left_x, right_x, 2*ky+1, mid+1, right_y, row, col, val);
            else
                update_y(kx, left_x, right_x, 2*ky, left_y, mid, row, col, val);
            tree2[kx][ky]=nzd(tree2[kx][2*ky], tree2[kx][2*ky+1]);
        }
    }
}

void update_x(int k, int left, int right, int row, int col, long long val) {
    if (left!=right) {
        int mid=(left+right)/2;
        if (row>mid) update_x(2*k+1, mid+1, right, row, col, val);
        else update_x(2*k, left, mid, row, col, val);
    }
    update_y(k, left, right, 1, 0, m-1, row, col, val);
}

void init(int r, int c) {
    n=r, m=c;
}

void update(int r, int c, long long br) {
    update_x(1, 0, n-1, r, c, br);
}

long long calculate(int x1, int y1, int x2, int y2) {
    long long rez=query_x(1, 0, n-1, x1, x2, y1, y2);
    return rez;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 1112 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1116 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 1116 KB Output is correct
10 Correct 1 ms 924 KB Output is correct
11 Correct 1 ms 856 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 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 447 ms 41824 KB Output is correct
5 Correct 331 ms 41808 KB Output is correct
6 Correct 383 ms 42688 KB Output is correct
7 Correct 390 ms 42248 KB Output is correct
8 Correct 309 ms 40532 KB Output is correct
9 Correct 374 ms 42492 KB Output is correct
10 Correct 328 ms 41824 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 368 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 1140 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 639 ms 45784 KB Output is correct
13 Correct 782 ms 37716 KB Output is correct
14 Correct 445 ms 6416 KB Output is correct
15 Correct 960 ms 86352 KB Output is correct
16 Correct 148 ms 130444 KB Output is correct
17 Correct 781 ms 111944 KB Output is correct
18 Correct 999 ms 131504 KB Output is correct
19 Correct 923 ms 131064 KB Output is correct
20 Correct 874 ms 130640 KB Output is correct
21 Correct 0 ms 600 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 1320 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1136 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 475 ms 42008 KB Output is correct
13 Correct 321 ms 41812 KB Output is correct
14 Correct 373 ms 42576 KB Output is correct
15 Correct 374 ms 42324 KB Output is correct
16 Correct 313 ms 40528 KB Output is correct
17 Correct 397 ms 42344 KB Output is correct
18 Correct 354 ms 42028 KB Output is correct
19 Correct 658 ms 45908 KB Output is correct
20 Correct 810 ms 37752 KB Output is correct
21 Correct 454 ms 6420 KB Output is correct
22 Correct 962 ms 86356 KB Output is correct
23 Correct 163 ms 130440 KB Output is correct
24 Correct 790 ms 111820 KB Output is correct
25 Correct 975 ms 131212 KB Output is correct
26 Correct 930 ms 131300 KB Output is correct
27 Correct 880 ms 130644 KB Output is correct
28 Runtime error 9 ms 344 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 0 ms 344 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1312 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 1216 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 456 ms 41792 KB Output is correct
13 Correct 323 ms 41812 KB Output is correct
14 Correct 386 ms 42576 KB Output is correct
15 Correct 403 ms 42320 KB Output is correct
16 Correct 312 ms 40636 KB Output is correct
17 Correct 458 ms 42488 KB Output is correct
18 Correct 341 ms 41924 KB Output is correct
19 Correct 670 ms 45908 KB Output is correct
20 Correct 814 ms 37616 KB Output is correct
21 Correct 474 ms 6424 KB Output is correct
22 Correct 974 ms 86152 KB Output is correct
23 Correct 157 ms 130404 KB Output is correct
24 Correct 798 ms 111888 KB Output is correct
25 Correct 971 ms 131280 KB Output is correct
26 Correct 899 ms 131124 KB Output is correct
27 Correct 850 ms 127632 KB Output is correct
28 Runtime error 8 ms 348 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -