답안 #56845 :: oj.uz

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

game

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

#define ll long long
#define MAXQ 10005
#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	3 ms	376 KB	Output is correct
2	Correct	4 ms	488 KB	Output is correct
3	Correct	4 ms	564 KB	Output is correct
4	Correct	3 ms	644 KB	Output is correct
5	Correct	2 ms	644 KB	Output is correct
6	Correct	4 ms	656 KB	Output is correct
7	Correct	2 ms	656 KB	Output is correct
8	Correct	2 ms	656 KB	Output is correct
9	Correct	3 ms	656 KB	Output is correct
10	Correct	3 ms	656 KB	Output is correct
11	Correct	3 ms	656 KB	Output is correct
12	Correct	3 ms	656 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	656 KB	Output is correct
2	Correct	2 ms	656 KB	Output is correct
3	Correct	2 ms	656 KB	Output is correct
4	Correct	1035 ms	13580 KB	Output is correct
5	Correct	541 ms	17956 KB	Output is correct
6	Correct	719 ms	19708 KB	Output is correct
7	Correct	966 ms	24128 KB	Output is correct
8	Correct	591 ms	25984 KB	Output is correct
9	Correct	1010 ms	32564 KB	Output is correct
10	Correct	799 ms	32564 KB	Output is correct
11	Correct	2 ms	32564 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	32564 KB	Output is correct
2	Correct	3 ms	32564 KB	Output is correct
3	Correct	4 ms	32564 KB	Output is correct
4	Correct	2 ms	32564 KB	Output is correct
5	Correct	2 ms	32564 KB	Output is correct
6	Correct	3 ms	32564 KB	Output is correct
7	Correct	2 ms	32564 KB	Output is correct
8	Correct	2 ms	32564 KB	Output is correct
9	Correct	3 ms	32564 KB	Output is correct
10	Correct	3 ms	32564 KB	Output is correct
11	Correct	3 ms	32564 KB	Output is correct
12	Correct	1441 ms	37528 KB	Output is correct
13	Correct	2677 ms	37528 KB	Output is correct
14	Correct	422 ms	37528 KB	Output is correct
15	Correct	3010 ms	43040 KB	Output is correct
16	Correct	338 ms	55200 KB	Output is correct
17	Correct	1836 ms	55200 KB	Output is correct
18	Correct	2152 ms	65720 KB	Output is correct
19	Correct	1938 ms	71216 KB	Output is correct
20	Correct	1720 ms	75884 KB	Output is correct
21	Correct	2 ms	75884 KB	Output is correct

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	75884 KB	Output is correct
2	Correct	3 ms	75884 KB	Output is correct
3	Correct	3 ms	75884 KB	Output is correct
4	Correct	2 ms	75884 KB	Output is correct
5	Correct	2 ms	75884 KB	Output is correct
6	Correct	3 ms	75884 KB	Output is correct
7	Correct	2 ms	75884 KB	Output is correct
8	Correct	3 ms	75884 KB	Output is correct
9	Correct	3 ms	75884 KB	Output is correct
10	Correct	3 ms	75884 KB	Output is correct
11	Correct	3 ms	75884 KB	Output is correct
12	Correct	712 ms	75884 KB	Output is correct
13	Correct	526 ms	75884 KB	Output is correct
14	Correct	973 ms	75884 KB	Output is correct
15	Correct	1087 ms	75884 KB	Output is correct
16	Correct	649 ms	75884 KB	Output is correct
17	Correct	894 ms	75884 KB	Output is correct
18	Correct	805 ms	75884 KB	Output is correct
19	Correct	1394 ms	75884 KB	Output is correct
20	Correct	2484 ms	75884 KB	Output is correct
21	Correct	583 ms	75884 KB	Output is correct
22	Correct	2970 ms	80820 KB	Output is correct
23	Correct	296 ms	93192 KB	Output is correct
24	Correct	1834 ms	93192 KB	Output is correct
25	Correct	2773 ms	103700 KB	Output is correct
26	Correct	2344 ms	109376 KB	Output is correct
27	Correct	2289 ms	111540 KB	Output is correct
28	Runtime error	3830 ms	257024 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
29	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

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

답안 #56845

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