oj.uz

Submission #56821

# Submission time Handle Problem Language Result Execution time Memory
56821 2018-07-12T16:45:25 Z hamzqq9 Game (IOI13_game) C++14
10 / 100
 13000 ms 2984 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));

    }

}

ll flag;

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

    if(OUTSIDE || !node) return ;

    if(INSIDE) {

        flag=__gcd(flag,S[node].GCD);
    
    }

    if(!VE) {

        get(SPLE),get(SPRI);

        return ;

    }

    if(!HO) {

        get(SPUP),get(SPDO);

        return ;

    }

    get(GOUP),get(GODO),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;
    
    get(1,0,0,R-1,C-1,P,Q,U,V);

    return flag;

}
/*
#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 4 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 420 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 3 ms 552 KB Output is correct
6 Correct 5 ms 580 KB Output is correct
7 Correct 4 ms 584 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 3 ms 752 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 3 ms 752 KB Output is correct
12 Correct 3 ms 752 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 752 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 3 ms 752 KB Output is correct
4 Execution timed out 13086 ms 2828 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2828 KB Output is correct
2 Correct 3 ms 2828 KB Output is correct
3 Correct 2 ms 2828 KB Output is correct
4 Correct 2 ms 2828 KB Output is correct
5 Correct 2 ms 2828 KB Output is correct
6 Correct 2 ms 2828 KB Output is correct
7 Correct 2 ms 2828 KB Output is correct
8 Correct 2 ms 2828 KB Output is correct
9 Correct 2 ms 2828 KB Output is correct
10 Correct 2 ms 2828 KB Output is correct
11 Correct 4 ms 2828 KB Output is correct
12 Execution timed out 13011 ms 2828 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2828 KB Output is correct
2 Correct 3 ms 2828 KB Output is correct
3 Correct 4 ms 2828 KB Output is correct
4 Correct 2 ms 2828 KB Output is correct
5 Correct 3 ms 2828 KB Output is correct
6 Correct 4 ms 2828 KB Output is correct
7 Correct 5 ms 2828 KB Output is correct
8 Correct 2 ms 2828 KB Output is correct
9 Correct 2 ms 2828 KB Output is correct
10 Correct 3 ms 2828 KB Output is correct
11 Correct 3 ms 2828 KB Output is correct
12 Execution timed out 13005 ms 2984 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2984 KB Output is correct
2 Correct 3 ms 2984 KB Output is correct
3 Correct 2 ms 2984 KB Output is correct
4 Correct 3 ms 2984 KB Output is correct
5 Correct 2 ms 2984 KB Output is correct
6 Correct 3 ms 2984 KB Output is correct
7 Correct 2 ms 2984 KB Output is correct
8 Correct 2 ms 2984 KB Output is correct
9 Correct 3 ms 2984 KB Output is correct
10 Correct 3 ms 2984 KB Output is correct
11 Correct 3 ms 2984 KB Output is correct
12 Execution timed out 13055 ms 2984 KB Time limit exceeded
13 Halted 0 ms 0 KB -