oj.uz

답안 #156916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
156916 2019-10-08T09:24:52 Z TAISA_ 게임 (IOI13_game) C++14
10 / 100
 2898 ms 86016 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 n = (1 << 11);
ll dat[4010][4010];
void upd(int x, int y, ll to) {
    int kx = x + n, ky = y + n;
    dat[kx][ky] = to;
    while (kx > 0) {
        if (kx < x + n) {
            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, n);
    }
    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) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dat[i][j] = 0;
        }
    }
}

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, n);
}

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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 41336 KB Output is correct
2 Correct 37 ms 42488 KB Output is correct
3 Correct 37 ms 42488 KB Output is correct
4 Correct 35 ms 41464 KB Output is correct
5 Correct 35 ms 41336 KB Output is correct
6 Correct 36 ms 42488 KB Output is correct
7 Correct 35 ms 41464 KB Output is correct
8 Correct 35 ms 41464 KB Output is correct
9 Correct 36 ms 42360 KB Output is correct
10 Correct 35 ms 41848 KB Output is correct
11 Correct 35 ms 41464 KB Output is correct
12 Correct 34 ms 41336 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 41336 KB Output is correct
2 Correct 34 ms 41336 KB Output is correct
3 Correct 35 ms 41464 KB Output is correct
4 Incorrect 332 ms 49712 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 44 ms 41312 KB Output is correct
2 Correct 37 ms 42460 KB Output is correct
3 Correct 43 ms 42488 KB Output is correct
4 Correct 42 ms 41336 KB Output is correct
5 Correct 36 ms 41464 KB Output is correct
6 Correct 37 ms 42472 KB Output is correct
7 Correct 35 ms 41464 KB Output is correct
8 Correct 36 ms 41448 KB Output is correct
9 Correct 36 ms 42360 KB Output is correct
10 Correct 42 ms 41848 KB Output is correct
11 Correct 41 ms 41492 KB Output is correct
12 Correct 1660 ms 83236 KB Output is correct
13 Correct 2898 ms 74988 KB Output is correct
14 Runtime error 140 ms 86016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 41460 KB Output is correct
2 Correct 44 ms 42488 KB Output is correct
3 Correct 37 ms 42460 KB Output is correct
4 Correct 35 ms 41340 KB Output is correct
5 Correct 36 ms 41336 KB Output is correct
6 Correct 36 ms 42488 KB Output is correct
7 Correct 42 ms 41436 KB Output is correct
8 Correct 35 ms 41464 KB Output is correct
9 Correct 36 ms 42392 KB Output is correct
10 Correct 36 ms 41848 KB Output is correct
11 Correct 35 ms 41464 KB Output is correct
12 Incorrect 326 ms 49572 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 41336 KB Output is correct
2 Correct 37 ms 42516 KB Output is correct
3 Correct 36 ms 42488 KB Output is correct
4 Correct 35 ms 41508 KB Output is correct
5 Correct 42 ms 41380 KB Output is correct
6 Correct 37 ms 42488 KB Output is correct
7 Correct 35 ms 41464 KB Output is correct
8 Correct 35 ms 41580 KB Output is correct
9 Correct 36 ms 42360 KB Output is correct
10 Correct 35 ms 41848 KB Output is correct
11 Correct 35 ms 41464 KB Output is correct
12 Incorrect 330 ms 49580 KB Output isn't correct
13 Halted 0 ms 0 KB -