답안 #56844 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56844	2018-07-12T20:14:44 Z	hamzqq9	게임 (IOI13_game)	C++14	63 / 100	3157 ms	257024 KB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define MAXQ 22005
#define orta ((bas+son)/2)

long long gcd2(long long X, long long Y) {
    if(X<Y) swap(X,Y);
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SEG2 {

    int L,R;

    ll GCD;

} S2[MAXQ*32*32];

struct SEG1 {

    int U,D;

    int SG2;

} S1[MAXQ*32];

int total2,total1,R,C;

ll get2(int node,int bas,int son,int Q,int V) {

    if(!node || bas>V || son<Q) return 0;

    if(bas>=Q && son<=V) return S2[node].GCD;

    return gcd2(get2(S2[node].L,bas,orta,Q,V),get2(S2[node].R,orta+1,son,Q,V));

}

ll get1(int node,int bas,int son,int P,int Q,int U,int V) {

    if(!node || bas>U || son<P) return 0;

    if(bas>=P && son<=U) {

        if(!S1[node].SG2) return 0;

        return get2(S1[node].SG2,0,C-1,Q,V);

    }

    return gcd2(get1(S1[node].U,bas,orta,P,Q,U,V),get1(S1[node].D,orta+1,son,P,Q,U,V));
 
}

void up2(int node,int bas,int son,int Q,ll K) {

    if(bas>Q || son<Q) return ;

    if(bas==Q && son==Q) {

        S2[node].GCD=K;

        return ;

    }

    if(!S2[node].L) {

        total2++;

        S2[node].L=total2;

    }

    if(!S2[node].R) {

        total2++;

        S2[node].R=total2;

    }

    up2(S2[node].L,bas,orta,Q,K);
    up2(S2[node].R,orta+1,son,Q,K);

    S2[node].GCD=gcd2(S2[S2[node].L].GCD,S2[S2[node].R].GCD);

}

void up1(int node,int bas,int son,int P,int Q,ll K) {

    if(bas>P || son<P) return ;

    if(bas==P && son==P) {

        if(!S1[node].SG2) {

            total2++;

            S1[node].SG2=total2;

        }

        up2(S1[node].SG2,0,C-1,Q,K);

        return ;

    }

    if(!S1[node].U) {

        total1++;

        S1[node].U=total1;

    }

    if(!S1[node].D) {

        total1++;

        S1[node].D=total1;

    }

    up1(S1[node].U,bas,orta,P,Q,K);
    up1(S1[node].D,orta+1,son,P,Q,K);

    if(!S1[node].SG2) {

        total2++;
        S1[node].SG2=total2;

    }

    K=gcd2(get2(S1[S1[node].U].SG2,0,C-1,Q,Q),get2(S1[S1[node].D].SG2,0,C-1,Q,Q));

    up2(S1[node].SG2,0,C-1,Q,K);

}

void init(int R, int C) {
    
    total1=1;

    ::R=R;
    ::C=C;

}

void update(int P, int Q, long long K) {

    up1(1,0,R-1,P,Q,K);

}

long long calculate(int P, int Q, int U, int V) {

    return get1(1,0,R-1,P,Q,U,V);

}
/*
#include <stdio.h>
#include <stdlib.h>
#include "game.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
    int res;

    FILE *f = fopen("game.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &R);
    res = fscanf(f, "%d", &C);
    res = fscanf(f, "%d", &N);

    init(R, C);

    for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
            res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
            res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("QUERY----> %lld\n", calculate(P, Q, U, V));
        } else
            fail("Invalid action type in input file.");
    }
    fclose(f);

    return 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	248 KB	Output is correct
2	Correct	4 ms	484 KB	Output is correct
3	Correct	4 ms	648 KB	Output is correct
4	Correct	3 ms	648 KB	Output is correct
5	Correct	3 ms	648 KB	Output is correct
6	Correct	3 ms	648 KB	Output is correct
7	Correct	4 ms	648 KB	Output is correct
8	Correct	2 ms	648 KB	Output is correct
9	Correct	3 ms	648 KB	Output is correct
10	Correct	3 ms	648 KB	Output is correct
11	Correct	3 ms	648 KB	Output is correct
12	Correct	3 ms	648 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	648 KB	Output is correct
2	Correct	2 ms	660 KB	Output is correct
3	Correct	3 ms	660 KB	Output is correct
4	Correct	936 ms	13648 KB	Output is correct
5	Correct	591 ms	17928 KB	Output is correct
6	Correct	751 ms	19552 KB	Output is correct
7	Correct	942 ms	23880 KB	Output is correct
8	Correct	637 ms	26036 KB	Output is correct
9	Correct	824 ms	32488 KB	Output is correct
10	Correct	859 ms	32488 KB	Output is correct
11	Correct	3 ms	32488 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	32488 KB	Output is correct
2	Correct	3 ms	32488 KB	Output is correct
3	Correct	3 ms	32488 KB	Output is correct
4	Correct	2 ms	32488 KB	Output is correct
5	Correct	3 ms	32488 KB	Output is correct
6	Correct	3 ms	32488 KB	Output is correct
7	Correct	2 ms	32488 KB	Output is correct
8	Correct	2 ms	32488 KB	Output is correct
9	Correct	4 ms	32488 KB	Output is correct
10	Correct	3 ms	32488 KB	Output is correct
11	Correct	3 ms	32488 KB	Output is correct
12	Correct	1351 ms	37444 KB	Output is correct
13	Correct	2557 ms	37444 KB	Output is correct
14	Correct	462 ms	37444 KB	Output is correct
15	Correct	3157 ms	42816 KB	Output is correct
16	Correct	381 ms	55244 KB	Output is correct
17	Correct	1709 ms	55244 KB	Output is correct
18	Correct	2471 ms	65768 KB	Output is correct
19	Correct	2294 ms	71464 KB	Output is correct
20	Correct	2153 ms	76172 KB	Output is correct
21	Correct	2 ms	76172 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	76172 KB	Output is correct
2	Correct	3 ms	76172 KB	Output is correct
3	Correct	3 ms	76172 KB	Output is correct
4	Correct	3 ms	76172 KB	Output is correct
5	Correct	2 ms	76172 KB	Output is correct
6	Correct	3 ms	76172 KB	Output is correct
7	Correct	3 ms	76172 KB	Output is correct
8	Correct	3 ms	76172 KB	Output is correct
9	Correct	3 ms	76172 KB	Output is correct
10	Correct	3 ms	76172 KB	Output is correct
11	Correct	3 ms	76172 KB	Output is correct
12	Correct	810 ms	76172 KB	Output is correct
13	Correct	600 ms	76172 KB	Output is correct
14	Correct	676 ms	76172 KB	Output is correct
15	Correct	758 ms	76172 KB	Output is correct
16	Correct	546 ms	76172 KB	Output is correct
17	Correct	821 ms	76172 KB	Output is correct
18	Correct	897 ms	76172 KB	Output is correct
19	Correct	1367 ms	76172 KB	Output is correct
20	Correct	2641 ms	76172 KB	Output is correct
21	Correct	475 ms	76172 KB	Output is correct
22	Correct	3014 ms	81016 KB	Output is correct
23	Correct	324 ms	93544 KB	Output is correct
24	Correct	1566 ms	93544 KB	Output is correct
25	Correct	2640 ms	104132 KB	Output is correct
26	Correct	2320 ms	109624 KB	Output is correct
27	Correct	2364 ms	114244 KB	Output is correct
28	Runtime error	1465 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.
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	3 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.
2	Halted	0 ms	0 KB	-

답안 #56844

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 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
0 / 17.0

Subtask #5
0 / 20.0