답안 #63789 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
63789	2018-08-02T19:47:32 Z	mohammad_kilani	게임 (IOI13_game)	C++17	80 / 100	10146 ms	257024 KB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 22001 , M = N * 30 * 19 + 10, L = N * 30;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[L][2];
int nxt1[L];
long long val , seg[M];
int nxt3[M][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_cols_3(int s,int e,int idx,int l,int r){
    if(l == -1 && r == -1)
        return;
    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((l != -1 && nxt3[l][1] != -1) || (r != -1 && nxt3[r][1] != -1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_3(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    if((l != -1 && nxt3[l][0] != -1) || (r != -1 && nxt3[r][0] != -1)){
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_3(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(nxt2[idx][0] == -1 || nxt2[idx][1] == -1) return;
    tmp1 = nxt2[idx][0];
    tmp2 = nxt2[idx][1];
    while((nxt2[tmp1][0] == -1) ^ (nxt2[tmp1][1] == -1)){
        if(nxt2[tmp1][0] == -1)
            tmp1 = nxt2[tmp1][1];
        else
            tmp1 = nxt2[tmp1][0];
    }
    if(tmp1 != -1)
        tmp1 = nxt1[tmp1];
    while((nxt2[tmp2][0] == -1) ^ (nxt2[tmp2][1] == -1)){
        if(nxt2[tmp2][0] == -1)
            tmp2 = nxt2[tmp2][1];
        else
            tmp2 = nxt2[tmp2][0];
    }
    if(tmp2 != -1)
        tmp2 = nxt1[tmp2];
    if(nxt1[idx] == -1){
        nxt1[idx] = addcol();
        update_cols_3(0, c , nxt1[idx], tmp1 , tmp2);
        return ;
    }
    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){
        if((nxt2[idx][0] == -1) ^ (nxt2[idx][1] == -1)){
            if(nxt2[idx][1] == -1)
                return get_rows(s,((s+e) >> 1),nxt2[idx][0]);
            return get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
        }
        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	2 ms	376 KB	Output is correct
2	Correct	3 ms	376 KB	Output is correct
3	Correct	3 ms	412 KB	Output is correct
4	Correct	3 ms	464 KB	Output is correct
5	Correct	3 ms	476 KB	Output is correct
6	Correct	4 ms	492 KB	Output is correct
7	Correct	2 ms	556 KB	Output is correct
8	Correct	2 ms	556 KB	Output is correct
9	Correct	4 ms	568 KB	Output is correct
10	Correct	3 ms	572 KB	Output is correct
11	Correct	4 ms	576 KB	Output is correct
12	Correct	3 ms	580 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	656 KB	Output is correct
2	Correct	3 ms	656 KB	Output is correct
3	Correct	3 ms	656 KB	Output is correct
4	Correct	766 ms	13504 KB	Output is correct
5	Correct	470 ms	15072 KB	Output is correct
6	Correct	871 ms	15072 KB	Output is correct
7	Correct	1088 ms	15072 KB	Output is correct
8	Correct	638 ms	15072 KB	Output is correct
9	Correct	1014 ms	15072 KB	Output is correct
10	Correct	954 ms	15072 KB	Output is correct
11	Correct	2 ms	15072 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	15072 KB	Output is correct
2	Correct	5 ms	15072 KB	Output is correct
3	Correct	3 ms	15072 KB	Output is correct
4	Correct	4 ms	15072 KB	Output is correct
5	Correct	3 ms	15072 KB	Output is correct
6	Correct	4 ms	15072 KB	Output is correct
7	Correct	3 ms	15072 KB	Output is correct
8	Correct	3 ms	15072 KB	Output is correct
9	Correct	3 ms	15072 KB	Output is correct
10	Correct	3 ms	15072 KB	Output is correct
11	Correct	3 ms	15072 KB	Output is correct
12	Correct	1093 ms	16440 KB	Output is correct
13	Correct	2965 ms	16440 KB	Output is correct
14	Correct	383 ms	16440 KB	Output is correct
15	Correct	3760 ms	16440 KB	Output is correct
16	Correct	1152 ms	16440 KB	Output is correct
17	Correct	1641 ms	16440 KB	Output is correct
18	Correct	2851 ms	16440 KB	Output is correct
19	Correct	2472 ms	16488 KB	Output is correct
20	Correct	1919 ms	16488 KB	Output is correct
21	Correct	3 ms	16488 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	16488 KB	Output is correct
2	Correct	3 ms	16488 KB	Output is correct
3	Correct	3 ms	16488 KB	Output is correct
4	Correct	5 ms	16488 KB	Output is correct
5	Correct	3 ms	16488 KB	Output is correct
6	Correct	3 ms	16488 KB	Output is correct
7	Correct	3 ms	16488 KB	Output is correct
8	Correct	3 ms	16488 KB	Output is correct
9	Correct	3 ms	16488 KB	Output is correct
10	Correct	3 ms	16488 KB	Output is correct
11	Correct	2 ms	16488 KB	Output is correct
12	Correct	782 ms	16488 KB	Output is correct
13	Correct	542 ms	16488 KB	Output is correct
14	Correct	1029 ms	16488 KB	Output is correct
15	Correct	1085 ms	16488 KB	Output is correct
16	Correct	619 ms	16488 KB	Output is correct
17	Correct	934 ms	16488 KB	Output is correct
18	Correct	803 ms	16488 KB	Output is correct
19	Correct	1300 ms	16488 KB	Output is correct
20	Correct	3063 ms	16488 KB	Output is correct
21	Correct	436 ms	16488 KB	Output is correct
22	Correct	3658 ms	16488 KB	Output is correct
23	Correct	1018 ms	16488 KB	Output is correct
24	Correct	1572 ms	16488 KB	Output is correct
25	Correct	2335 ms	16488 KB	Output is correct
26	Correct	1949 ms	16488 KB	Output is correct
27	Correct	2134 ms	16488 KB	Output is correct
28	Correct	982 ms	53964 KB	Output is correct
29	Correct	2577 ms	68288 KB	Output is correct
30	Correct	8764 ms	68288 KB	Output is correct
31	Correct	7879 ms	68288 KB	Output is correct
32	Correct	732 ms	68288 KB	Output is correct
33	Correct	1022 ms	68288 KB	Output is correct
34	Correct	1478 ms	68288 KB	Output is correct
35	Correct	2548 ms	68288 KB	Output is correct
36	Correct	3923 ms	68288 KB	Output is correct
37	Correct	3520 ms	68288 KB	Output is correct
38	Correct	2810 ms	68288 KB	Output is correct
39	Correct	2486 ms	68288 KB	Output is correct
40	Correct	3 ms	68288 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	68288 KB	Output is correct
2	Correct	10 ms	68288 KB	Output is correct
3	Correct	4 ms	68288 KB	Output is correct
4	Correct	3 ms	68288 KB	Output is correct
5	Correct	1 ms	68288 KB	Output is correct
6	Correct	3 ms	68288 KB	Output is correct
7	Correct	3 ms	68288 KB	Output is correct
8	Correct	3 ms	68288 KB	Output is correct
9	Correct	3 ms	68288 KB	Output is correct
10	Correct	3 ms	68288 KB	Output is correct
11	Correct	4 ms	68288 KB	Output is correct
12	Correct	706 ms	68288 KB	Output is correct
13	Correct	527 ms	68288 KB	Output is correct
14	Correct	834 ms	68288 KB	Output is correct
15	Correct	973 ms	68288 KB	Output is correct
16	Correct	632 ms	68288 KB	Output is correct
17	Correct	939 ms	68288 KB	Output is correct
18	Correct	738 ms	68288 KB	Output is correct
19	Correct	1343 ms	68288 KB	Output is correct
20	Correct	3046 ms	68288 KB	Output is correct
21	Correct	423 ms	68288 KB	Output is correct
22	Correct	3904 ms	68288 KB	Output is correct
23	Correct	1091 ms	68288 KB	Output is correct
24	Correct	1455 ms	68288 KB	Output is correct
25	Correct	2467 ms	68288 KB	Output is correct
26	Correct	2145 ms	68288 KB	Output is correct
27	Correct	1890 ms	68288 KB	Output is correct
28	Correct	1006 ms	68288 KB	Output is correct
29	Correct	2731 ms	68288 KB	Output is correct
30	Correct	7881 ms	68288 KB	Output is correct
31	Correct	8267 ms	68288 KB	Output is correct
32	Correct	733 ms	68288 KB	Output is correct
33	Correct	1006 ms	68288 KB	Output is correct
34	Correct	1746 ms	104596 KB	Output is correct
35	Correct	2312 ms	104596 KB	Output is correct
36	Correct	4179 ms	125308 KB	Output is correct
37	Correct	3724 ms	136052 KB	Output is correct
38	Correct	3709 ms	146184 KB	Output is correct
39	Correct	1362 ms	203132 KB	Output is correct
40	Correct	4681 ms	245300 KB	Output is correct
41	Correct	10146 ms	245300 KB	Output is correct
42	Correct	9629 ms	245300 KB	Output is correct
43	Runtime error	1946 ms	257024 KB	Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
44	Halted	0 ms	0 KB	-

답안 #63789

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 20.0