답안 #56820 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56820	2018-07-12T16:41:24 Z	hamzqq9	게임 (IOI13_game)	C++14	37 / 100	13000 ms	10536 KB

game

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

#define ll long long
#define MAXIMUM 63*200005

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 SEG {

    int U,D,L,R;
    ll GCD;

} S[MAXIMUM];

int total=1;
int C,R;

#define CLASSIC ux,uy,dx,dy
#define GOUP S[node].U,bx,by,(bx+sx)/2,(by+sy)/2,CLASSIC
#define GODO S[node].D,bx,(by+sy)/2+1,(bx+sx)/2,sy,CLASSIC
#define GOLE S[node].L,(bx+sx)/2+1,by,sx,(by+sy)/2,CLASSIC
#define GORI S[node].R,(bx+sx)/2+1,(by+sy)/2+1,sx,sy,CLASSIC
#define SPLE S[node].L,bx,by,sx,(by+sy)/2,CLASSIC
#define SPRI S[node].R,bx,(by+sy)/2+1,sx,sy,CLASSIC
#define SPUP S[node].U,bx,by,(bx+sx)/2,sy,CLASSIC
#define SPDO S[node].D,(bx+sx)/2+1,by,sx,sy,CLASSIC
#define INSIDE bx>=ux && by>=uy && sx<=dx && sy<=dy
#define OUTSIDE sx<ux || sy<uy || bx>dx || by>dy
#define HO (by<sy)
#define VE (bx<sx)

void up(int node,int bx,int by,int sx,int sy,int ux,int uy,int dx,int dy,ll val) {

    //printf("NODE--> %d BX--> %d BY-->%d SX-->%d SY-->%d\n",node,bx,by,sx,sy);

    if(OUTSIDE) return ;

    if(INSIDE) {

     //   printf("NODE-->%d\n",node);

        S[node].GCD=val;

        return ;

    }

    if(!S[node].U && VE) {

        total++;

        S[node].U=total;

    }

    if(!S[node].D && VE) {

        total++;

        S[node].D=total;

    }

    if(!S[node].L && HO) {

        total++;

        S[node].L=total;

    }

    if(!S[node].R && HO) {

        total++;

        S[node].R=total;
    
    }

    if(!VE) {

        up(SPLE,val);
        up(SPRI,val);

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

    }
    else if(!HO) {

        up(SPUP,val);
        up(SPDO,val);

        S[node].GCD=gcd2(S[S[node].U].GCD,S[S[node].D].GCD);

    }
    else {

        up(GOLE,val);
        up(GORI,val);
        up(GOUP,val);
        up(GODO,val);

        S[node].GCD=gcd2(gcd2(S[S[node].L].GCD,S[S[node].R].GCD),gcd2(S[S[node].U].GCD,S[S[node].D].GCD));

    }

}

bool flag=0;

ll get(int node,int bx,int by,int sx,int sy,int ux,int uy,int dx,int dy) {

    if(flag) return 0;

    if(OUTSIDE || !node) return 0;

    if(INSIDE) {

        if(S[node].GCD==1) flag=1;

        return S[node].GCD;
    
    }

    if(!VE) {

        return gcd2(get(SPLE),get(SPRI));

    }

    if(!HO) {

        return gcd2(get(SPUP),get(SPDO));

    }

    return gcd2(gcd2(get(GOUP),get(GODO)),gcd2(get(GOLE),get(GORI)));

}

void init(int R, int C) {
    
    ::R=R;
    ::C=C;
    S[1].GCD=S[1].U=S[1].D=S[1].L=S[1].R=0;

}

void update(int P, int Q, long long K) {
    
    up(1,0,0,R-1,C-1,P,Q,P,Q,K);

   // printf("%lld\n\n",S[1].GCD);

}

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

    flag=0;
    
    return get(1,0,0,R-1,C-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	3 ms	496 KB	Output is correct
3	Correct	3 ms	496 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	3 ms	564 KB	Output is correct
6	Correct	4 ms	612 KB	Output is correct
7	Correct	4 ms	616 KB	Output is correct
8	Correct	3 ms	620 KB	Output is correct
9	Correct	3 ms	624 KB	Output is correct
10	Correct	3 ms	652 KB	Output is correct
11	Correct	3 ms	664 KB	Output is correct
12	Correct	2 ms	664 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	668 KB	Output is correct
2	Correct	2 ms	672 KB	Output is correct
3	Correct	3 ms	672 KB	Output is correct
4	Correct	1756 ms	9848 KB	Output is correct
5	Correct	1224 ms	10140 KB	Output is correct
6	Correct	1621 ms	10140 KB	Output is correct
7	Correct	1906 ms	10140 KB	Output is correct
8	Correct	1173 ms	10140 KB	Output is correct
9	Correct	1365 ms	10140 KB	Output is correct
10	Correct	376 ms	10140 KB	Output is correct
11	Correct	2 ms	10140 KB	Output is correct

Subtask #3
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10140 KB	Output is correct
2	Correct	2 ms	10140 KB	Output is correct
3	Correct	2 ms	10140 KB	Output is correct
4	Correct	2 ms	10140 KB	Output is correct
5	Correct	2 ms	10140 KB	Output is correct
6	Correct	2 ms	10140 KB	Output is correct
7	Correct	3 ms	10140 KB	Output is correct
8	Correct	2 ms	10140 KB	Output is correct
9	Correct	2 ms	10140 KB	Output is correct
10	Correct	2 ms	10140 KB	Output is correct
11	Correct	2 ms	10140 KB	Output is correct
12	Correct	11849 ms	10140 KB	Output is correct
13	Execution timed out	13062 ms	10140 KB	Time limit exceeded
14	Halted	0 ms	0 KB	-

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10140 KB	Output is correct
2	Correct	3 ms	10140 KB	Output is correct
3	Correct	2 ms	10140 KB	Output is correct
4	Correct	2 ms	10140 KB	Output is correct
5	Correct	2 ms	10140 KB	Output is correct
6	Correct	2 ms	10140 KB	Output is correct
7	Correct	2 ms	10140 KB	Output is correct
8	Correct	2 ms	10140 KB	Output is correct
9	Correct	2 ms	10140 KB	Output is correct
10	Correct	2 ms	10140 KB	Output is correct
11	Correct	2 ms	10140 KB	Output is correct
12	Correct	1173 ms	10140 KB	Output is correct
13	Correct	804 ms	10536 KB	Output is correct
14	Correct	1018 ms	10536 KB	Output is correct
15	Correct	1168 ms	10536 KB	Output is correct
16	Correct	717 ms	10536 KB	Output is correct
17	Correct	1074 ms	10536 KB	Output is correct
18	Correct	340 ms	10536 KB	Output is correct
19	Correct	11874 ms	10536 KB	Output is correct
20	Execution timed out	13054 ms	10536 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	10536 KB	Output is correct
2	Correct	3 ms	10536 KB	Output is correct
3	Correct	3 ms	10536 KB	Output is correct
4	Correct	2 ms	10536 KB	Output is correct
5	Correct	2 ms	10536 KB	Output is correct
6	Correct	2 ms	10536 KB	Output is correct
7	Correct	2 ms	10536 KB	Output is correct
8	Correct	2 ms	10536 KB	Output is correct
9	Correct	3 ms	10536 KB	Output is correct
10	Correct	2 ms	10536 KB	Output is correct
11	Correct	3 ms	10536 KB	Output is correct
12	Correct	1123 ms	10536 KB	Output is correct
13	Correct	818 ms	10536 KB	Output is correct
14	Correct	1024 ms	10536 KB	Output is correct
15	Correct	1159 ms	10536 KB	Output is correct
16	Correct	819 ms	10536 KB	Output is correct
17	Correct	1160 ms	10536 KB	Output is correct
18	Correct	335 ms	10536 KB	Output is correct
19	Correct	11610 ms	10536 KB	Output is correct
20	Execution timed out	13100 ms	10536 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

답안 #56820

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 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
0 / 26.0

Subtask #4
0 / 17.0

Subtask #5
0 / 20.0