oj.uz

답안 #63785

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
63785 2018-08-02T18:58:35 Z mohammad_kilani 게임 (IOI13_game) C++17
80 / 100
 9319 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 22001 ;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[N * 30][2];
int nxt1[N * 30];
long long val , seg[N * 30 * 20];
int nxt3[N * 30 * 20][2];

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

inline int addrow(){
    nxt1[rowscnt] = -1;
    nxt2[rowscnt][0] = nxt2[rowscnt][1] = -1;
    return rowscnt++;
}

inline int addcol(){
    seg[colscnt] = 0;
    nxt3[colscnt][0] = nxt3[colscnt][1] = -1;
    return colscnt++;
}

void update_cols(int s,int e,int idx){
    if(s == e){
        seg[idx] = val;
        return;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols(((s+e) >> 1) + 1, e, nxt3[idx][1]);
    }
    else{
         if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols(s,((s+e) >> 1),nxt3[idx][0]);
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}

void update_cols_2(int s,int e,int idx,int l,int r){
    if(s == e){
        seg[idx] = 0;
        if(l != -1) seg[idx] = gcd2(seg[idx],seg[l]);
        if(r != -1) seg[idx] = gcd2(seg[idx],seg[r]);
        return ;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_2(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    else{
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_2(s , ((s+e) >> 1) , nxt3[idx][0],(l == -1 ? -1 : nxt3[l][0]) , (r == -1 ? -1 : nxt3[r][0]));
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);

}

void update_rows(int s,int e,int idx){
    if(s == e){
        if(nxt1[idx] == -1)
            nxt1[idx] = addcol();
        update_cols(0 , c , nxt1[idx]);
        return;
    }
    if(r1 > ((s + e) >> 1)){
        if(nxt2[idx][1] == -1)
            nxt2[idx][1] = addrow();
        update_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
    }
    else{
        if(nxt2[idx][0] == -1)
            nxt2[idx][0] = addrow();
        update_rows(s , ((s+e) >> 1), nxt2[idx][0]);
    }
    if(nxt1[idx] == -1)
            nxt1[idx] = addcol();
    tmp1 = nxt2[idx][0];
    tmp2 = nxt2[idx][1];
    if(tmp1 != -1)
        tmp1 = nxt1[tmp1];
    if(tmp2 != -1)
        tmp2 = nxt1[tmp2];
    update_cols_2(0 , c , nxt1[idx] , tmp1 , tmp2);
}

long long get_cols(int s,int e,int idx){
    if(s > c2 || e < c1 || idx == -1)
        return 0;
    if(s >= c1 && e <= c2)
        return seg[idx];
    return gcd2(get_cols(s,((s+e) >> 1),nxt3[idx][0]),get_cols(((s+e) >> 1) + 1, e,nxt3[idx][1]));
}

long long get_rows(int s,int e,int idx){
    if(s > r2 || e < r1 || idx == -1)
        return 0;
    if(s >= r1 && e <= r2){
        return get_cols(0 , c , nxt1[idx]);
    }
    return gcd2(get_rows(s,((s+e) >> 1),nxt2[idx][0]),get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]));
}


void init(int R, int C) {
    /*long double cur = sizeof(seg) + sizeof(nxt1) + sizeof(nxt2) + sizeof(nxt3);
    cur = cur / (1024.0 * 1024.0);
    cout << fixed << cur << endl;
    */
    r = R ;
    c = C;
    addrow();
}

void update(int P, int Q, long long K) {
    r1 = P;
    c1 = Q;
    val = K;
    update_rows(0 , r , 0);
}

long long calculate(int P, int Q, int U, int V) {
    r1 = P;
    r2 = U;
    c1 = Q;
    c2 = V;
    return get_rows(0 , r , 0);
}

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 3 ms 380 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 564 KB Output is correct
4 Correct 3 ms 652 KB Output is correct
5 Correct 4 ms 652 KB Output is correct
6 Correct 3 ms 652 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 4 ms 752 KB Output is correct
12 Correct 3 ms 752 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 764 KB Output is correct
3 Correct 3 ms 764 KB Output is correct
4 Correct 700 ms 13400 KB Output is correct
5 Correct 598 ms 15332 KB Output is correct
6 Correct 868 ms 15332 KB Output is correct
7 Correct 1201 ms 15332 KB Output is correct
8 Correct 607 ms 15332 KB Output is correct
9 Correct 1008 ms 15332 KB Output is correct
10 Correct 979 ms 15332 KB Output is correct
11 Correct 3 ms 15332 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 15332 KB Output is correct
2 Correct 3 ms 15332 KB Output is correct
3 Correct 4 ms 15332 KB Output is correct
4 Correct 3 ms 15332 KB Output is correct
5 Correct 3 ms 15332 KB Output is correct
6 Correct 4 ms 15332 KB Output is correct
7 Correct 3 ms 15332 KB Output is correct
8 Correct 4 ms 15332 KB Output is correct
9 Correct 3 ms 15332 KB Output is correct
10 Correct 4 ms 15332 KB Output is correct
11 Correct 4 ms 15332 KB Output is correct
12 Correct 1534 ms 16204 KB Output is correct
13 Correct 3399 ms 16204 KB Output is correct
14 Correct 460 ms 16204 KB Output is correct
15 Correct 3907 ms 16204 KB Output is correct
16 Correct 1006 ms 16204 KB Output is correct
17 Correct 1604 ms 16204 KB Output is correct
18 Correct 3152 ms 16444 KB Output is correct
19 Correct 2752 ms 16540 KB Output is correct
20 Correct 2324 ms 16540 KB Output is correct
21 Correct 2 ms 16540 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 16540 KB Output is correct
2 Correct 3 ms 16540 KB Output is correct
3 Correct 3 ms 16540 KB Output is correct
4 Correct 2 ms 16540 KB Output is correct
5 Correct 2 ms 16540 KB Output is correct
6 Correct 3 ms 16540 KB Output is correct
7 Correct 4 ms 16540 KB Output is correct
8 Correct 3 ms 16540 KB Output is correct
9 Correct 3 ms 16540 KB Output is correct
10 Correct 2 ms 16540 KB Output is correct
11 Correct 4 ms 16540 KB Output is correct
12 Correct 825 ms 16540 KB Output is correct
13 Correct 558 ms 16540 KB Output is correct
14 Correct 1048 ms 16540 KB Output is correct
15 Correct 1098 ms 16540 KB Output is correct
16 Correct 631 ms 16540 KB Output is correct
17 Correct 1143 ms 16540 KB Output is correct
18 Correct 876 ms 16540 KB Output is correct
19 Correct 1324 ms 16540 KB Output is correct
20 Correct 3185 ms 16540 KB Output is correct
21 Correct 390 ms 16540 KB Output is correct
22 Correct 3513 ms 16540 KB Output is correct
23 Correct 1030 ms 16540 KB Output is correct
24 Correct 1513 ms 16540 KB Output is correct
25 Correct 2809 ms 16540 KB Output is correct
26 Correct 2419 ms 16540 KB Output is correct
27 Correct 2166 ms 16540 KB Output is correct
28 Correct 1221 ms 131980 KB Output is correct
29 Correct 2764 ms 147040 KB Output is correct
30 Correct 9309 ms 147040 KB Output is correct
31 Correct 8393 ms 147040 KB Output is correct
32 Correct 881 ms 147040 KB Output is correct
33 Correct 1501 ms 147040 KB Output is correct
34 Correct 1939 ms 147040 KB Output is correct
35 Correct 2635 ms 147040 KB Output is correct
36 Correct 4979 ms 147040 KB Output is correct
37 Correct 4088 ms 147040 KB Output is correct
38 Correct 3851 ms 147040 KB Output is correct
39 Correct 3425 ms 147040 KB Output is correct
40 Correct 3 ms 147040 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 147040 KB Output is correct
2 Correct 3 ms 147040 KB Output is correct
3 Correct 4 ms 147040 KB Output is correct
4 Correct 3 ms 147040 KB Output is correct
5 Correct 4 ms 147040 KB Output is correct
6 Correct 3 ms 147040 KB Output is correct
7 Correct 2 ms 147040 KB Output is correct
8 Correct 3 ms 147040 KB Output is correct
9 Correct 3 ms 147040 KB Output is correct
10 Correct 3 ms 147040 KB Output is correct
11 Correct 2 ms 147040 KB Output is correct
12 Correct 777 ms 147040 KB Output is correct
13 Correct 498 ms 147040 KB Output is correct
14 Correct 955 ms 147040 KB Output is correct
15 Correct 1122 ms 147040 KB Output is correct
16 Correct 688 ms 147040 KB Output is correct
17 Correct 1119 ms 147040 KB Output is correct
18 Correct 932 ms 147040 KB Output is correct
19 Correct 1376 ms 147040 KB Output is correct
20 Correct 3210 ms 147040 KB Output is correct
21 Correct 581 ms 147040 KB Output is correct
22 Correct 4086 ms 147040 KB Output is correct
23 Correct 1052 ms 147040 KB Output is correct
24 Correct 1628 ms 147040 KB Output is correct
25 Correct 2904 ms 147040 KB Output is correct
26 Correct 2447 ms 147040 KB Output is correct
27 Correct 2289 ms 147040 KB Output is correct
28 Correct 1405 ms 147040 KB Output is correct
29 Correct 3294 ms 147044 KB Output is correct
30 Correct 9311 ms 147044 KB Output is correct
31 Correct 9319 ms 147044 KB Output is correct
32 Correct 877 ms 147044 KB Output is correct
33 Correct 1275 ms 147044 KB Output is correct
34 Correct 1667 ms 183228 KB Output is correct
35 Correct 2874 ms 183228 KB Output is correct
36 Correct 4819 ms 203940 KB Output is correct
37 Correct 4006 ms 214892 KB Output is correct
38 Correct 3812 ms 224856 KB Output is correct
39 Runtime error 4161 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -