oj.uz

Submission #237835

# Submission time Handle Problem Language Result Execution time Memory
237835 2020-06-09T01:29:36 Z mohamedsobhi777 Game (IOI13_game) C++14
0 / 100
 43 ms 67704 KB 
#include<bits/stdc++.h>
#include "game.h"
 
#define maxc 1000000000
#define maxr 1000000000
 
using namespace std ; 
 
const int N =100000 + 7 ;
 
int n , count_nodes ; 
 
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
long long tree[N * 4 * 10 ] , lc[N * 4 * 10 ] , rc[N * 4 * 10 ] ;

struct dynamic_segmentree{
 
        long long iden = 0 ; 
 
        long long f(long long x , long long y){
                return gcd2(x , y) ; 
        }
 
        void update(int node , int L , int R , int ix , long long val){

                if(L == R){
                        tree[node] = val ; 
                        return ; 
                }
 
                int mid = (L+R) >>1 ; 
                if(ix<=mid){
                        if(lc[node] == -1)
                                lc[node] = ++count_nodes ; 
                        update(lc[node] , L , mid , ix , val) ; 
                }
                else{
                        if(rc[node] == -1)
                                rc[node] = ++count_nodes ; 
                        update(rc[node] , mid+1 , R , ix , val) ; 
                }
 
                if(lc[node] == -1)
                        tree[node] = tree[rc[node]] ; 
                else if(rc[node] == -1)
                        tree[node] = tree[lc[node]] ; 
                else tree[node] = f(tree[lc[node]] , tree[rc[node]]) ; 
        }
 
        long long query(int node , int L , int R , int l , int r){
                if(l > R || r < L || node == -1)
                        return iden ; 
                if(L>=l && R<=r)
                        return tree[node] ;
                int mid = (L+R) >>1 ; 
                long long s1 = query(lc[node]  , L , mid , l , r) ; 
                long long s2 = query(rc[node] , mid+1 , R , l , r) ; 
                return f(s1 , s2) ;
        }
 
} ; 
dynamic_segmentree d[N * 4] ;  
int LC[N * 4] , RC[N*4] ; 
int countsegs ; 
int root[N * 4] ; 

void sharp_update(int x , int y , int val){
        if(root[x] == -1) 
                root[x] = ++ count_nodes ; 
        d[x].update(root[x] ,1 , maxc , y , val) ; 
}


void update2d(int node , int L , int R , int ix , int ix2, long long val){

        if(L == R){
                sharp_update(node , ix2 , val) ; 
                return ; 
        }
 
        int mid = (L+R) >>1 ; 

        if(ix<=mid){
                if(LC[node] == -1)
                        LC[node] = ++countsegs ; 
                update2d(LC[node] , L , mid , ix , ix2 , val) ; 
        }
        else{
                if(rc[node] == -1)
                        RC[node] = ++countsegs ;
                update2d(RC[node] , mid+ 1, R , ix , ix2 , val) ; 
        } 
        sharp_update(node , ix2 , val) ; 
                
}
 
long long query(int node , int L , int R , int l , int r , int l1 , int r1){
        if(l > R || r < L || node == -1)
                return 0LL; 
        if(L>=l && R<=r)
                return d[node].query(root[node] , 1 , maxc , l1 , r1) ;
        int mid = (L+R) >>1 ; 
        long long s1 = query(LC[node]  , L , mid , l , r , l1 , r1) ; 
        long long s2 = query(RC[node] , mid+1 , R , l , r , l1 , r1) ; 
        return gcd2(s1 , s2) ; 
}


void update(int a , int b , long long c){
        update2d( 0 , 1 , maxr , a + 1 , b + 1, c) ; 
}

 
long long calculate(int a , int b , int c , int e){
        return query(0 , 1 , maxr , a +1, c +1, b +1, e  +1) ; 
}
 
void init(int R, int C) {
        memset(root , -1 , sizeof root) ;
        memset(lc ,-1 , sizeof lc) ; 
        memset(rc , -1 , sizeof rc) ;
        memset(LC , -1 , sizeof LC) ; 
        memset(RC , -1 , sizeof RC) ;  
}

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 67704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 67704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 67704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 67704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 67704 KB Output isn't correct
2 Halted 0 ms 0 KB -