oj.uz

답안 #56817

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
56817 2018-07-12T16:24:36 Z hamzqq9 게임 (IOI13_game) C++14
37 / 100
 13000 ms 115264 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define MAXIMUM 63*100005

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;
        S[total].GCD=S[total].U=S[total].D=S[total].L=S[total].R=0;

    }

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

        total++;

        S[node].D=total;
        S[total].GCD=S[total].U=S[total].D=S[total].L=S[total].R=0;

    }

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

        total++;

        S[node].L=total;
        S[total].GCD=S[total].U=S[total].D=S[total].L=S[total].R=0;

    }

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

        total++;

        S[node].R=total;
        S[total].GCD=S[total].U=S[total].D=S[total].L=S[total].R=0;
    
    }

    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 380 KB Output is correct
2 Correct 3 ms 472 KB Output is correct
3 Correct 3 ms 472 KB Output is correct
4 Correct 2 ms 472 KB Output is correct
5 Correct 2 ms 472 KB Output is correct
6 Correct 2 ms 472 KB Output is correct
7 Correct 2 ms 476 KB Output is correct
8 Correct 3 ms 572 KB Output is correct
9 Correct 2 ms 572 KB Output is correct
10 Correct 2 ms 572 KB Output is correct
11 Correct 2 ms 632 KB Output is correct
12 Correct 2 ms 632 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 644 KB Output is correct
2 Correct 2 ms 644 KB Output is correct
3 Correct 3 ms 772 KB Output is correct
4 Correct 1468 ms 12164 KB Output is correct
5 Correct 1083 ms 16364 KB Output is correct
6 Correct 1475 ms 17996 KB Output is correct
7 Correct 1391 ms 22436 KB Output is correct
8 Correct 706 ms 26020 KB Output is correct
9 Correct 1075 ms 31420 KB Output is correct
10 Correct 945 ms 35780 KB Output is correct
11 Correct 2 ms 35780 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 43212 KB Output is correct
2 Correct 3 ms 43212 KB Output is correct
3 Correct 2 ms 43212 KB Output is correct
4 Correct 2 ms 43212 KB Output is correct
5 Correct 3 ms 43212 KB Output is correct
6 Correct 2 ms 43212 KB Output is correct
7 Correct 2 ms 43212 KB Output is correct
8 Correct 2 ms 43212 KB Output is correct
9 Correct 3 ms 43212 KB Output is correct
10 Correct 3 ms 43212 KB Output is correct
11 Correct 3 ms 43212 KB Output is correct
12 Correct 1368 ms 49256 KB Output is correct
13 Correct 815 ms 53612 KB Output is correct
14 Correct 1043 ms 55100 KB Output is correct
15 Correct 1457 ms 59544 KB Output is correct
16 Correct 852 ms 63124 KB Output is correct
17 Correct 1305 ms 68620 KB Output is correct
18 Correct 1090 ms 73028 KB Output is correct
19 Execution timed out 13087 ms 80212 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 80212 KB Output is correct
2 Correct 3 ms 80212 KB Output is correct
3 Correct 3 ms 80212 KB Output is correct
4 Correct 2 ms 80212 KB Output is correct
5 Correct 2 ms 80212 KB Output is correct
6 Correct 2 ms 80212 KB Output is correct
7 Correct 2 ms 80212 KB Output is correct
8 Correct 2 ms 80212 KB Output is correct
9 Correct 2 ms 80212 KB Output is correct
10 Correct 2 ms 80212 KB Output is correct
11 Correct 2 ms 80212 KB Output is correct
12 Correct 1189 ms 84608 KB Output is correct
13 Correct 803 ms 88836 KB Output is correct
14 Correct 964 ms 90344 KB Output is correct
15 Correct 1267 ms 94800 KB Output is correct
16 Correct 731 ms 98268 KB Output is correct
17 Correct 1109 ms 103904 KB Output is correct
18 Correct 1344 ms 108052 KB Output is correct
19 Execution timed out 13005 ms 115264 KB Time limit exceeded
20 Halted 0 ms 0 KB -