oj.uz

Submission #1091137

# Submission time Handle Problem Language Result Execution time Memory
1091137 2024-09-19T22:45:07 Z kkkkkkkk Game (IOI13_game) C++14
37 / 100
 821 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long n, m;
vector<vector<long long> > tree;

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 (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);
}

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 (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]);
    }
}

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) {
    tree.resize(4*r, vector<long long> (4*c, 0));
    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;
}
/*
int main()
{
    init(2, 3);
    update(0, 0, 20);
    update(0, 2, 15);
    update(1, 1, 12);
    cout << calculate(0, 0, 0, 2) << endl;
    cout << calculate(0, 0, 1, 1) << endl;
    update(0, 1, 6);
    update(1, 1, 14);
    cout << calculate(0, 0, 0, 2) << endl;
    cout << calculate(0, 0, 1, 1) << endl;

    return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 448 ms 129672 KB Output is correct
5 Correct 344 ms 130072 KB Output is correct
6 Correct 409 ms 128848 KB Output is correct
7 Correct 404 ms 128848 KB Output is correct
8 Correct 347 ms 128848 KB Output is correct
9 Correct 390 ms 128848 KB Output is correct
10 Correct 379 ms 128828 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 638 ms 129856 KB Output is correct
13 Correct 799 ms 126548 KB Output is correct
14 Runtime error 123 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 460 ms 129720 KB Output is correct
13 Correct 344 ms 130044 KB Output is correct
14 Correct 420 ms 128732 KB Output is correct
15 Correct 393 ms 128852 KB Output is correct
16 Correct 347 ms 128852 KB Output is correct
17 Correct 407 ms 128848 KB Output is correct
18 Correct 375 ms 128848 KB Output is correct
19 Correct 632 ms 129872 KB Output is correct
20 Correct 817 ms 126520 KB Output is correct
21 Runtime error 121 ms 256000 KB Execution killed with signal 9
22 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 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1624 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 1 ms 1628 KB Output is correct
12 Correct 470 ms 129676 KB Output is correct
13 Correct 338 ms 129916 KB Output is correct
14 Correct 418 ms 128872 KB Output is correct
15 Correct 414 ms 128852 KB Output is correct
16 Correct 378 ms 128852 KB Output is correct
17 Correct 412 ms 128720 KB Output is correct
18 Correct 358 ms 128852 KB Output is correct
19 Correct 649 ms 129720 KB Output is correct
20 Correct 821 ms 126544 KB Output is correct
21 Runtime error 118 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -