답안 #56819 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56819	2018-07-12T16:28:32 Z	hamzqq9	게임 (IOI13_game)	C++14	37 / 100	13000 ms	12852 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));

    }

}

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

    if(OUTSIDE || !node) return 0;

    if(INSIDE) 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) {
    
    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	2 ms	248 KB	Output is correct
2	Correct	3 ms	360 KB	Output is correct
3	Correct	2 ms	440 KB	Output is correct
4	Correct	2 ms	540 KB	Output is correct
5	Correct	3 ms	540 KB	Output is correct
6	Correct	3 ms	660 KB	Output is correct
7	Correct	3 ms	660 KB	Output is correct
8	Correct	3 ms	660 KB	Output is correct
9	Correct	2 ms	720 KB	Output is correct
10	Correct	3 ms	720 KB	Output is correct
11	Correct	2 ms	748 KB	Output is correct
12	Correct	2 ms	748 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	748 KB	Output is correct
2	Correct	2 ms	748 KB	Output is correct
3	Correct	2 ms	748 KB	Output is correct
4	Correct	1368 ms	10656 KB	Output is correct
5	Correct	807 ms	10940 KB	Output is correct
6	Correct	1232 ms	10940 KB	Output is correct
7	Correct	1538 ms	10940 KB	Output is correct
8	Correct	974 ms	10940 KB	Output is correct
9	Correct	1381 ms	10940 KB	Output is correct
10	Correct	927 ms	10940 KB	Output is correct
11	Correct	3 ms	10940 KB	Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10940 KB	Output is correct
2	Correct	3 ms	10940 KB	Output is correct
3	Correct	2 ms	10940 KB	Output is correct
4	Correct	2 ms	10940 KB	Output is correct
5	Correct	2 ms	10940 KB	Output is correct
6	Correct	2 ms	10940 KB	Output is correct
7	Correct	3 ms	10940 KB	Output is correct
8	Correct	2 ms	10940 KB	Output is correct
9	Correct	3 ms	10940 KB	Output is correct
10	Correct	4 ms	10940 KB	Output is correct
11	Correct	3 ms	10940 KB	Output is correct
12	Correct	1235 ms	10940 KB	Output is correct
13	Correct	799 ms	10964 KB	Output is correct
14	Correct	1286 ms	10964 KB	Output is correct
15	Correct	1348 ms	10964 KB	Output is correct
16	Correct	751 ms	10964 KB	Output is correct
17	Correct	1281 ms	10964 KB	Output is correct
18	Correct	1331 ms	10964 KB	Output is correct
19	Correct	12291 ms	10964 KB	Output is correct
20	Execution timed out	13100 ms	10964 KB	Time limit exceeded
21	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	10964 KB	Output is correct
2	Correct	3 ms	10964 KB	Output is correct
3	Correct	3 ms	10964 KB	Output is correct
4	Correct	2 ms	10964 KB	Output is correct
5	Correct	2 ms	10964 KB	Output is correct
6	Correct	2 ms	10964 KB	Output is correct
7	Correct	2 ms	10964 KB	Output is correct
8	Correct	2 ms	10964 KB	Output is correct
9	Correct	2 ms	10964 KB	Output is correct
10	Correct	3 ms	10964 KB	Output is correct
11	Correct	2 ms	10964 KB	Output is correct
12	Correct	1183 ms	12404 KB	Output is correct
13	Correct	912 ms	12852 KB	Output is correct
14	Correct	1175 ms	12852 KB	Output is correct
15	Correct	1634 ms	12852 KB	Output is correct
16	Correct	991 ms	12852 KB	Output is correct
17	Correct	1472 ms	12852 KB	Output is correct
18	Correct	1208 ms	12852 KB	Output is correct
19	Execution timed out	13004 ms	12852 KB	Time limit exceeded
20	Halted	0 ms	0 KB	-

답안 #56819

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