oj.uz

Submission #156917

# Submission time Handle Problem Language Result Execution time Memory
156917 2019-10-08T09:30:39 Z TAISA_ Game (IOI13_game) C++14
0 / 100
 4 ms 904 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int nx, ny;
vector<vector<ll>> dat;
void upd(int x, int y, ll to) {
    int kx = x + nx, ky = y + ny;
    dat[kx][ky] = to;
    while (kx > 0) {
        if (kx < x + nx) {
            dat[kx][ky] = gcd2(dat[kx << 1][ky], dat[kx << 1 | 1][ky]);
        }
        int k = ky;
        k >>= 1;
        while (k > 0) {
            dat[kx][k] = gcd2(dat[kx][k << 1], dat[kx][k << 1 | 1]);
            k >>= 1;
        }
        kx >>= 1;
    }
}

ll getx(int x1, int y1, int x2, int y2, int ky, int k, int l, int r) {
    if (x2 <= l || r <= x1) {
        return 0;
    }
    if (x1 <= l && r <= x2) {
        return dat[k][ky];
    }
    ll vl = getx(x1, y1, x2, y2, ky, k << 1, l, (l + r) / 2);
    ll vr = getx(x1, y1, x2, y2, ky, k << 1 | 1, (l + r) / 2, r);
    return gcd2(vl, vr);
}

ll gety(int x1, int y1, int x2, int y2, int k, int l, int r) {
    if (y2 <= l || r <= y1) {
        return 0;
    }
    if (y1 <= l && r <= y2) {
        return getx(x1, y1, x2, y2, k, 1, 0, ny);
    }
    ll vl = gety(x1, y1, x2, y2, k << 1, l, (l + r) / 2);
    ll vr = gety(x1, y1, x2, y2, k << 1 | 1, (l + r) / 2, r);
    return gcd2(vl, vr);
}

void init(int R, int C) {
    ++R;
    ++C;
    nx = 1;
    while (nx < R) {
        nx <<= 1;
    }
    ny = 1;
    while (ny < C) {
        ny <<= 1;
    }
    dat.resize(2 * nx);
    for (int i = 0; i < 2 * nx; i++) {
        dat[i].resize(2 * ny);
    }
}

void update(int P, int Q, long long K) { upd(P, Q, K); }

long long calculate(int P, int Q, int U, int V) {
    return gety(P, Q, U + 1, V + 1, 1, 0, nx);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 3 ms 552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 904 KB Output is correct
7 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 764 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Runtime error 2 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -