oj.uz

답안 #254218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254218 2020-07-29T14:42:23 Z AaronNaidu 게임 (IOI13_game) C++14
36 / 100
 1995 ms 126072 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;

int r, c, p, q, u, v;
ll segTree[4096][4096];

void init(int R, int C) {
    r = R;
    c = C;
}

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

void update(int p, int q, ll k) {
    p += 2048;
    q += 2048;
    segTree[p][q] = k;
    while (q > 0)
    {
        //cout << "Outerwhile q = " << q << "\n";
        int pTemp = p/2;
        while (pTemp > 0)
        {
            //cout <<"Innerwhile p temp = " << pTemp << "\n";
            segTree[pTemp][q] = gcd2(segTree[2*pTemp][q], segTree[2*pTemp+1][q]);
            pTemp /= 2;
        }
        q /= 2;
        segTree[p][q] = gcd2(segTree[p][2*q], segTree[p][2*q+1]);
        //cout << "End of outerwhile q = " << q << "\n";
    }

}

ll getSegTree(int nodex, int nodey, int nodexstart, int nodexend, int nodeystart, int nodeyend) {
    if (nodexstart > u or nodexend < p or nodeystart > v or nodeyend < q)
    {
        return 0;
    }
    if (nodexstart >= p and nodexend <= u)
    {
        if (nodeystart >= q and nodeyend <= v)
        {
            return segTree[nodex][nodey];
        }
        int midy = (nodeystart + nodeyend)/2;
        return gcd2(getSegTree(nodex, 2*nodey, nodexstart, nodexend, nodeystart, midy), getSegTree(nodex, 2*nodey+1, nodexstart, nodexend, midy+1, nodeyend));
    }
    int midx = (nodexstart + nodexend)/2;
    return gcd2(getSegTree(2*nodex, nodey, nodexstart, midx, nodeystart, nodeyend), getSegTree(2*nodex+1, nodey, midx + 1, nodexend, nodeystart, nodeyend));
}    
    
ll calculate(int P, int Q, int U, int V) {
    p = P;
    q = Q;
    u = U;
    v = V;
    return getSegTree(1, 1, 0, 2047, 0, 2047);
}

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 1 ms 512 KB Output is correct
2 Correct 3 ms 3072 KB Output is correct
3 Correct 2 ms 3072 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 3072 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 3 ms 3072 KB Output is correct
10 Correct 2 ms 2048 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Correct 0 ms 512 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Incorrect 250 ms 12668 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 3 ms 3072 KB Output is correct
3 Correct 3 ms 3072 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 3072 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 2 ms 2048 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Correct 1164 ms 62816 KB Output is correct
13 Correct 1591 ms 54520 KB Output is correct
14 Correct 809 ms 8728 KB Output is correct
15 Correct 1750 ms 76832 KB Output is correct
16 Correct 430 ms 124408 KB Output is correct
17 Correct 1576 ms 110240 KB Output is correct
18 Correct 1995 ms 125820 KB Output is correct
19 Correct 1845 ms 126072 KB Output is correct
20 Correct 1684 ms 124912 KB Output is correct
21 Correct 1 ms 512 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 2 ms 3072 KB Output is correct
4 Correct 0 ms 512 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 3072 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 3 ms 2048 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Incorrect 250 ms 12536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 3 ms 3072 KB Output is correct
3 Correct 4 ms 3072 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 3072 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 2 ms 3072 KB Output is correct
10 Correct 2 ms 2048 KB Output is correct
11 Correct 1 ms 896 KB Output is correct
12 Incorrect 242 ms 12528 KB Output isn't correct
13 Halted 0 ms 0 KB -