oj.uz

Submission #1040247

# Submission time Handle Problem Language Result Execution time Memory
1040247 2024-07-31T19:51:39 Z ArthuroWich Game (IOI13_game) C++17
36 / 100
 810 ms 139140 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int gcd2(int X, int Y) {
    int tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int seg[4*2005][4*2005];
void updatey(int nx, int ny, int l, int r, int lx, int rx, int y, int v) {
    if (l == r) {
        if (lx == rx) {
            seg[nx][ny] = v;
        } else {
            seg[nx][ny] = gcd2(seg[2*nx][ny], seg[2*nx+1][ny]);
        }
    } else {
        int m = (l+r)/2;
        if (l <= y && y <= m) {
            updatey(nx, 2*ny, l, m, lx, rx, y, v);
        } else {
            updatey(nx, 2*ny+1, m+1, r, lx, rx, y, v);
        }
        seg[nx][ny] = gcd2(seg[nx][2*ny], seg[nx][2*ny+1]);
    }
}
void updatex(int nx, int l, int r, int x, int y, int v) {
    if (l != r) {
        int m = (l+r)/2;
        if (l <= x && x <= m) {
            updatex(2*nx, l, m, x, y, v);
        } else {
            updatex(2*nx+1, m+1, r, x, y, v);
        }
        seg[nx][1] = gcd2(seg[2*nx][1], seg[2*nx+1][1]);
    }
    updatey(nx, 1, 0, 2000, l, r, y, v);
}
int queryy(int nx, int ny, int l, int r, int ay, int by) {
    if (by < l || r < ay) {
        return 0;
    } else if (ay <= l && r <= by) {
        return seg[nx][ny];
    } else {
        int m = (l+r)/2;
        return gcd2(queryy(nx, 2*ny, l, m, ay, by), queryy(nx, 2*ny+1, m+1, r, ay, by));
    }
}
int queryx(int nx, int l, int r, int ax, int bx, int ay, int by) {
    if (bx < l || r < ax) {
        return 0;
    } else if (ax <= l && r <= bx) {
        return queryy(nx, 1, 0, 2000, ay, by);
    } else {
        int m = (l+r)/2;
        return gcd2(queryx(2*nx, l, m, ax, bx, ay, by), queryx(2*nx+1, m+1, r, ax, bx, ay, by));
    }
}
void init(int32_t R, int32_t C) {

}
void update(int32_t P, int32_t Q, int K) {
    updatex(1, 0, 2000, P, Q, K);
}
int calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
    return queryx(1, 0, 2000, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 1 ms 11868 KB Output is correct
11 Correct 1 ms 10844 KB Output is correct
12 Correct 1 ms 10588 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 1 ms 10588 KB Output is correct
3 Correct 1 ms 10584 KB Output is correct
4 Incorrect 97 ms 16460 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 1 ms 10584 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 10588 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 11868 KB Output is correct
11 Correct 1 ms 11092 KB Output is correct
12 Correct 558 ms 63816 KB Output is correct
13 Correct 709 ms 59872 KB Output is correct
14 Correct 384 ms 18516 KB Output is correct
15 Correct 808 ms 95104 KB Output is correct
16 Correct 324 ms 137176 KB Output is correct
17 Correct 654 ms 114516 KB Output is correct
18 Correct 809 ms 138836 KB Output is correct
19 Correct 810 ms 139140 KB Output is correct
20 Correct 737 ms 138020 KB Output is correct
21 Correct 1 ms 10588 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10584 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 1 ms 10688 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 1 ms 12124 KB Output is correct
10 Correct 2 ms 11868 KB Output is correct
11 Correct 1 ms 10844 KB Output is correct
12 Incorrect 104 ms 16492 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 10588 KB Output is correct
2 Correct 2 ms 12124 KB Output is correct
3 Correct 2 ms 12380 KB Output is correct
4 Correct 1 ms 10684 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 11952 KB Output is correct
7 Correct 1 ms 10588 KB Output is correct
8 Correct 1 ms 6748 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 11864 KB Output is correct
11 Correct 1 ms 10844 KB Output is correct
12 Incorrect 96 ms 16576 KB Output isn't correct
13 Halted 0 ms 0 KB -