oj.uz

Submission #56822

# Submission time Handle Problem Language Result Execution time Memory
56822 2018-07-12T16:46:04 Z hamzqq9 Game (IOI13_game) C++14
37 / 100
 13000 ms 10460 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);

        return ;
    
    }

    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 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 432 KB Output is correct
4 Correct 2 ms 432 KB Output is correct
5 Correct 3 ms 464 KB Output is correct
6 Correct 3 ms 540 KB Output is correct
7 Correct 2 ms 544 KB Output is correct
8 Correct 3 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 2 ms 620 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 3 ms 620 KB Output is correct
4 Correct 1923 ms 10036 KB Output is correct
5 Correct 1278 ms 10320 KB Output is correct
6 Correct 1085 ms 10320 KB Output is correct
7 Correct 1127 ms 10320 KB Output is correct
8 Correct 698 ms 10320 KB Output is correct
9 Correct 1351 ms 10320 KB Output is correct
10 Correct 1322 ms 10320 KB Output is correct
11 Correct 2 ms 10320 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10320 KB Output is correct
2 Correct 3 ms 10320 KB Output is correct
3 Correct 3 ms 10320 KB Output is correct
4 Correct 2 ms 10320 KB Output is correct
5 Correct 3 ms 10320 KB Output is correct
6 Correct 2 ms 10320 KB Output is correct
7 Correct 2 ms 10320 KB Output is correct
8 Correct 3 ms 10320 KB Output is correct
9 Correct 2 ms 10320 KB Output is correct
10 Correct 2 ms 10320 KB Output is correct
11 Correct 4 ms 10320 KB Output is correct
12 Correct 1524 ms 10320 KB Output is correct
13 Correct 1215 ms 10460 KB Output is correct
14 Correct 1083 ms 10460 KB Output is correct
15 Correct 1082 ms 10460 KB Output is correct
16 Correct 609 ms 10460 KB Output is correct
17 Correct 1016 ms 10460 KB Output is correct
18 Correct 1008 ms 10460 KB Output is correct
19 Execution timed out 13053 ms 10460 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10460 KB Output is correct
2 Correct 3 ms 10460 KB Output is correct
3 Correct 2 ms 10460 KB Output is correct
4 Correct 2 ms 10460 KB Output is correct
5 Correct 5 ms 10460 KB Output is correct
6 Correct 3 ms 10460 KB Output is correct
7 Correct 2 ms 10460 KB Output is correct
8 Correct 2 ms 10460 KB Output is correct
9 Correct 2 ms 10460 KB Output is correct
10 Correct 4 ms 10460 KB Output is correct
11 Correct 3 ms 10460 KB Output is correct
12 Correct 1614 ms 10460 KB Output is correct
13 Correct 1271 ms 10460 KB Output is correct
14 Correct 1060 ms 10460 KB Output is correct
15 Correct 1086 ms 10460 KB Output is correct
16 Correct 671 ms 10460 KB Output is correct
17 Correct 1036 ms 10460 KB Output is correct
18 Correct 1063 ms 10460 KB Output is correct
19 Execution timed out 13083 ms 10460 KB Time limit exceeded
20 Halted 0 ms 0 KB -