oj.uz

Submission #56820

# Submission time Handle Problem Language Result Execution time Memory
56820 2018-07-12T16:41:24 Z hamzqq9 Game (IOI13_game) C++14
37 / 100
 13000 ms 10536 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -