oj.uz

Submission #1091138

# Submission time Handle Problem Language Result Execution time Memory
1091138 2024-09-19T22:51:39 Z kkkkkkkk Game (IOI13_game) C++14
63 / 100
 1002 ms 133804 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 0 ms 348 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 2 ms 1372 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 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 1112 KB Output is correct
10 Correct 1 ms 856 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 448 KB Output is correct
4 Correct 453 ms 41572 KB Output is correct
5 Correct 335 ms 41812 KB Output is correct
6 Correct 361 ms 42388 KB Output is correct
7 Correct 383 ms 42160 KB Output is correct
8 Correct 307 ms 40276 KB Output is correct
9 Correct 378 ms 42064 KB Output is correct
10 Correct 340 ms 41556 KB Output is correct
11 Correct 0 ms 348 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 2 ms 1368 KB Output is correct
4 Correct 0 ms 372 KB Output is correct
5 Correct 0 ms 448 KB Output is correct
6 Correct 1 ms 1116 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 0 ms 604 KB Output is correct
12 Correct 692 ms 45900 KB Output is correct
13 Correct 790 ms 37816 KB Output is correct
14 Correct 446 ms 8456 KB Output is correct
15 Correct 952 ms 88144 KB Output is correct
16 Correct 156 ms 132180 KB Output is correct
17 Correct 785 ms 114332 KB Output is correct
18 Correct 1002 ms 133716 KB Output is correct
19 Correct 932 ms 133556 KB Output is correct
20 Correct 880 ms 133064 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.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 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 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 0 ms 448 KB Output is correct
12 Correct 450 ms 41648 KB Output is correct
13 Correct 341 ms 41812 KB Output is correct
14 Correct 389 ms 42324 KB Output is correct
15 Correct 395 ms 42116 KB Output is correct
16 Correct 318 ms 40272 KB Output is correct
17 Correct 399 ms 42320 KB Output is correct
18 Correct 340 ms 41684 KB Output is correct
19 Correct 658 ms 45740 KB Output is correct
20 Correct 790 ms 37656 KB Output is correct
21 Correct 485 ms 8432 KB Output is correct
22 Correct 973 ms 88188 KB Output is correct
23 Correct 160 ms 132176 KB Output is correct
24 Correct 791 ms 114256 KB Output is correct
25 Correct 961 ms 133804 KB Output is correct
26 Correct 963 ms 133716 KB Output is correct
27 Correct 883 ms 133052 KB Output is correct
28 Runtime error 8 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 1 ms 344 KB Output is correct
2 Correct 1 ms 1212 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 1220 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 448 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 0 ms 604 KB Output is correct
12 Correct 472 ms 41644 KB Output is correct
13 Correct 328 ms 41752 KB Output is correct
14 Correct 377 ms 42324 KB Output is correct
15 Correct 393 ms 42264 KB Output is correct
16 Correct 324 ms 40276 KB Output is correct
17 Correct 376 ms 42068 KB Output is correct
18 Correct 335 ms 41700 KB Output is correct
19 Correct 659 ms 45844 KB Output is correct
20 Correct 779 ms 37660 KB Output is correct
21 Correct 452 ms 8360 KB Output is correct
22 Correct 969 ms 88268 KB Output is correct
23 Correct 171 ms 132180 KB Output is correct
24 Correct 818 ms 114172 KB Output is correct
25 Correct 999 ms 133728 KB Output is correct
26 Correct 926 ms 133716 KB Output is correct
27 Correct 950 ms 133172 KB Output is correct
28 Runtime error 8 ms 348 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -