oj.uz

답안 #402699

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402699 2021-05-12T09:17:30 Z prvocislo 게임 (IOI13_game) C++17
36 / 100
 13000 ms 132196 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 * 2, vector<ll>(c * 2, 0));
}
void update(int x, int y, long long k) {
    x += r;
    update_1d(y, k, st[x]);
    for (x = (x >> 1); x > 0; x >>= 1)
        for (int i = 0; i < c * 2; i++) st[x][i] = gcd(st[x << 1][i], st[x << 1 | 1][i]);
}
long long calculate(int lx, int ly, int rx, int ry) {
    ll g = 0;
    for (lx += r, rx += r + 1; lx < rx; lx >>= 1, rx >>= 1) {
        if (lx & 1) g = gcd(g, query_1d(ly, ry, st[lx++]));
        if (rx & 1) g = gcd(g, query_1d(ly, ry, st[--rx]));
    }
    return g;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Execution timed out 13047 ms 38676 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 588 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 2 ms 608 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1359 ms 39744 KB Output is correct
13 Correct 1542 ms 36256 KB Output is correct
14 Correct 1052 ms 130928 KB Output is correct
15 Correct 2604 ms 130764 KB Output is correct
16 Correct 4710 ms 130676 KB Output is correct
17 Correct 2192 ms 131784 KB Output is correct
18 Correct 5069 ms 132008 KB Output is correct
19 Correct 5014 ms 132196 KB Output is correct
20 Correct 5645 ms 131748 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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