oj.uz

답안 #402645

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402645 2021-05-12T07:27:54 Z prvocislo 게임 (IOI13_game) C++17
37 / 100
 13000 ms 24616 KB 
#include "game.h"
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;

long long gcd(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X, X = Y, Y = tmp % Y;
    }
    return X;
}
int r, c;
void update_1d(int i, ll k, vector<ll>& v){
    v[i + c] = k;
    for (i = ((i + c) >> 1); i > 0; i >>= 1) v[i] = gcd(v[i << 1], v[i << 1 | 1]);
}
ll query_1d(int li, int ri, vector<ll>& v) {
    ll g = 0;
    for (li += c, ri += c + 1; li < ri; li >>= 1, ri >>= 1) {
        if (li & 1) g = gcd(g, v[li++]);
        if (ri & 1) g = gcd(g, v[--ri]);
    } return g;
}
vector<vector<ll> > st;
void init(int R, int C) {
    r = R, c = C; 
    st.assign(r, vector<ll>(c * 2, 0));
}
void update(int x, int y, long long k) {
    update_1d(y, k, st[x]);
}
long long calculate(int lx, int ly, int rx, int ry) {
    ll g = 0;
    for (int x = lx; x <= rx; x++)
        g = gcd(g, query_1d(ly, ry, st[x]));
    return g;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 416 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 420 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 550 ms 24328 KB Output is correct
5 Correct 327 ms 24160 KB Output is correct
6 Correct 500 ms 21696 KB Output is correct
7 Correct 525 ms 21412 KB Output is correct
8 Correct 413 ms 21752 KB Output is correct
9 Correct 513 ms 21424 KB Output is correct
10 Correct 454 ms 21052 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Execution timed out 13091 ms 21164 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 551 ms 24356 KB Output is correct
13 Correct 353 ms 24232 KB Output is correct
14 Correct 504 ms 21796 KB Output is correct
15 Correct 525 ms 21464 KB Output is correct
16 Correct 399 ms 21708 KB Output is correct
17 Correct 526 ms 21544 KB Output is correct
18 Correct 471 ms 21156 KB Output is correct
19 Execution timed out 13083 ms 21300 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 424 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 551 ms 24616 KB Output is correct
13 Correct 330 ms 24188 KB Output is correct
14 Correct 522 ms 21636 KB Output is correct
15 Correct 525 ms 21428 KB Output is correct
16 Correct 402 ms 21796 KB Output is correct
17 Correct 519 ms 21516 KB Output is correct
18 Correct 441 ms 21032 KB Output is correct
19 Execution timed out 13085 ms 21304 KB Time limit exceeded
20 Halted 0 ms 0 KB -