oj.uz

Submission #1091136

# Submission time Handle Problem Language Result Execution time Memory
1091136 2024-09-19T22:41:40 Z kkkkkkkk Game (IOI13_game) C++14
37 / 100
 801 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(long long kx, long long ky, long long left, long long right, long long levo_kol, long long desno_kol) {
    if (left>=levo_kol && right<=desno_kol)
        return tree[kx][ky];
    else if (left>desno_kol || right<levo_kol)
        return 0;
    long long 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(long long k, long long left, long long right, long long gore_red, long long dole_red, long long levo_kol, long long 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;
    long long 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(long long kx, long long left_x, long long right_x, long long ky, long long left_y, long long right_y, long long row, long long 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 {
        long long 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(long long k, long long left, long long right, long long row, long long col, long long val) {
    if (left!=right) {
        long long 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 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 1 ms 604 KB Output is correct
9 Correct 1 ms 1672 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 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 478 ms 134012 KB Output is correct
5 Correct 333 ms 133908 KB Output is correct
6 Correct 396 ms 131348 KB Output is correct
7 Correct 449 ms 131120 KB Output is correct
8 Correct 398 ms 131604 KB Output is correct
9 Correct 417 ms 131096 KB Output is correct
10 Correct 358 ms 130836 KB Output is correct
11 Correct 0 ms 344 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 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 344 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 674 ms 133836 KB Output is correct
13 Correct 780 ms 130388 KB Output is correct
14 Runtime error 110 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 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 1 ms 600 KB Output is correct
5 Correct 1 ms 1624 KB Output is correct
6 Correct 1 ms 1456 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 452 ms 134128 KB Output is correct
13 Correct 351 ms 133908 KB Output is correct
14 Correct 415 ms 131348 KB Output is correct
15 Correct 421 ms 131240 KB Output is correct
16 Correct 348 ms 131600 KB Output is correct
17 Correct 405 ms 131100 KB Output is correct
18 Correct 363 ms 130736 KB Output is correct
19 Correct 633 ms 133968 KB Output is correct
20 Correct 784 ms 130444 KB Output is correct
21 Runtime error 116 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 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 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 526 ms 134204 KB Output is correct
13 Correct 355 ms 133948 KB Output is correct
14 Correct 424 ms 131608 KB Output is correct
15 Correct 398 ms 131064 KB Output is correct
16 Correct 354 ms 131592 KB Output is correct
17 Correct 422 ms 131172 KB Output is correct
18 Correct 380 ms 130836 KB Output is correct
19 Correct 665 ms 133968 KB Output is correct
20 Correct 801 ms 130432 KB Output is correct
21 Runtime error 104 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -