oj.uz

답안 #400245

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
400245 2021-05-07T18:00:03 Z Antekb 게임 (IOI13_game) C++14
63 / 100
 2453 ms 256000 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N=(1<<30), M=8e6;

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 wsk1=1;
int l1[M], r1[M];
ll val1[M];

void upd(int v){
    if(!v)return;
    val1[v]=gcd2(val1[l1[v]], val1[r1[v]]);
}
ll quer1d(int v, int L, int R, int l, int r){
    if(!v)return 0;
    //cout<<L<<" "<<R<<" "<<v->val<<"q\n";
    if(l==L && r==R){
        return val1[v];
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(l1[v], L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(r1[v], M+1, R, max(l, M+1), r));
    return ans;
}
int upd1d(int v, int L, int R, int i, ll val){
    if(!v)v=wsk1++;
    if(L==R){
        //cout<<v->val<<" "<<val<<" "<<i<<"u\n";
        val1[v]=val;
        return v;
    }
    //cout<<L<<" "<<R<<" "<<v->val<<"a\n";
    int M=(L+R)>>1;
    if(i<=M)l1[v]=upd1d(l1[v], L, M, i, val);
    else r1[v]=upd1d(r1[v], M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"b\n";
    return v;
}

int wsk2=1;
int l2[M], r2[M], val2[M];

ll quer2d(int v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(val2[v], 0, N-1, x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(l2[v], L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(r2[v], M+1, R, max(l, M+1), r, x, y));
    return ans;
}

int upd2d(int v, int L, int R, int i, int j, ll val){
    if(!v)v=wsk2++;
    if(L==R){
        val2[v]=upd1d(val2[v], 0, N-1, j, val);
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)l2[v]=upd2d(l2[v], L, M, i, j, val);
    else r2[v]=upd2d(r2[v], M+1, R, i, j, val);
    val2[v]=upd1d(val2[v], 0, N-1, j, gcd2(quer1d(val2[l2[v]], 0, N-1, j, j), quer1d(val2[r2[v]], 0, N-1, j, j)));
    return v;
}
int root=0;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    root=upd2d(root, 0, N-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return quer2d(root, 0, N-1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 995 ms 28504 KB Output is correct
5 Correct 786 ms 28976 KB Output is correct
6 Correct 927 ms 25844 KB Output is correct
7 Correct 965 ms 25404 KB Output is correct
8 Correct 641 ms 16740 KB Output is correct
9 Correct 986 ms 25668 KB Output is correct
10 Correct 937 ms 25136 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 304 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1587 ms 12888 KB Output is correct
13 Correct 2171 ms 6256 KB Output is correct
14 Correct 701 ms 2372 KB Output is correct
15 Correct 2416 ms 8600 KB Output is correct
16 Correct 820 ms 13480 KB Output is correct
17 Correct 1165 ms 10212 KB Output is correct
18 Correct 1842 ms 13824 KB Output is correct
19 Correct 1651 ms 13992 KB Output is correct
20 Correct 1595 ms 13216 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 985 ms 28620 KB Output is correct
13 Correct 783 ms 28944 KB Output is correct
14 Correct 939 ms 25760 KB Output is correct
15 Correct 969 ms 25572 KB Output is correct
16 Correct 641 ms 16760 KB Output is correct
17 Correct 965 ms 25668 KB Output is correct
18 Correct 942 ms 25200 KB Output is correct
19 Correct 1595 ms 12984 KB Output is correct
20 Correct 2154 ms 6564 KB Output is correct
21 Correct 675 ms 2348 KB Output is correct
22 Correct 2413 ms 8620 KB Output is correct
23 Correct 817 ms 13468 KB Output is correct
24 Correct 1149 ms 10212 KB Output is correct
25 Correct 1838 ms 13892 KB Output is correct
26 Correct 1647 ms 13892 KB Output is correct
27 Correct 1572 ms 13296 KB Output is correct
28 Correct 803 ms 132420 KB Output is correct
29 Runtime error 1977 ms 256000 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 1044 ms 27904 KB Output is correct
13 Correct 781 ms 28100 KB Output is correct
14 Correct 977 ms 25028 KB Output is correct
15 Correct 1026 ms 24904 KB Output is correct
16 Correct 659 ms 16068 KB Output is correct
17 Correct 1030 ms 24896 KB Output is correct
18 Correct 988 ms 24612 KB Output is correct
19 Correct 1598 ms 12124 KB Output is correct
20 Correct 2146 ms 5636 KB Output is correct
21 Correct 678 ms 1732 KB Output is correct
22 Correct 2453 ms 7944 KB Output is correct
23 Correct 817 ms 12824 KB Output is correct
24 Correct 1177 ms 9680 KB Output is correct
25 Correct 1958 ms 12996 KB Output is correct
26 Correct 1711 ms 13252 KB Output is correct
27 Correct 1649 ms 12668 KB Output is correct
28 Correct 827 ms 132800 KB Output is correct
29 Runtime error 2064 ms 256000 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -