oj.uz

Submission #253094

# Submission time Handle Problem Language Result Execution time Memory
253094 2020-07-26T21:56:57 Z test2 Game (IOI13_game) C++14
0 / 100
 12 ms 19968 KB 
#include "game.h"
#include<bits/stdc++.h>

const int N = 1e5 + 7 ; 
using namespace std ; 

int n; 
int nodes = 1 ;
long long tree[N * 4 * 10] ;
int l[10 * N][2] , r[10 * N][2] ;
int heads[10 * N] ; 

int h = 0 ; 

int head(int x){
        if(heads[x] == -1)
                heads[x] = nodes ++ ; 
        return heads[x] ;
}

void init(int R , int C){
        memset(l , -1 , sizeof l) ; 
        memset(r , -1 , sizeof r) ;
        memset(heads , -1 , sizeof heads) ;
}


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 f(long long x, long long y){
        return gcd2(x , y); 
}

int Left(int x , int  i = 0){
        if(l[x][i] == -1){
                l[x][i] = nodes ++ ;
        }       
        return l[x][i] ; 
}

int Right(int x , int i = 0 ){
        if(r[x][i] == -1){
                r[x][i] = nodes ++ ; 
        }
        return r[x][i] ; 
}

void update(int node , int L , int R , int idx , long long val){

        if(L == R){
                tree[node] = val ; 
                return ; 
        }
        int mid = (L + R ) >> 1 ; 
        
        if(idx <= mid)
                update( Left(node), L ,mid , idx ,val) ;
        else
                update( Right(node) , mid +1 , R , idx , val) ;
        
        if(l[node][0] == -1)tree[node] = tree[r[node][0]] ; 
        else if(r[node][0] == -1)tree[node] = tree[l[node][0]] ;
        else tree[node] = f(tree[l[node][0]] ,  tree[r[node][0]] )  ; 
        return ; 
}

long long query(int node , int L , int R , int l ,int r){
        if(l > r || l > R || r < L || node == -1)
                return 0 ;
        if(L >= l && R<= r){
                return tree[node] ;
        }
        int mid = (L + R) >> 1; 
        long long s1 = query(Left(node) , L , mid , l , r) ; 
        long long s2 = query(Right(node) , mid+1 ,R , l , r) ; 
        return f(s1 , s2) ; 
}

int segs = 1 ; 

void upd(int node , int L , int R , int idX , int idY , long long val){

        if(L == R){
                update( head(node) , 1 , N , idY , val) ;
                return ;
        }
        int mid = (L + R) >> 1; 
        if(idX<= mid){
                upd( Left(node , 1) , L , mid , idX , idY , val) ; 
        }
        else{
                upd( Right(node , 1) , mid+1 , R , idX , idY , val) ; 
        }
        update(head(node) , 1 , N , idY , val) ; 
}

long long query2(int node , int L , int R , int l , int r , int x ,int y){ 
        if(node == -1)
                return 0 ; 
        if(l > r|| l > R || r < L)
                return 0 ; 

        if(L>= l && R<=r ){
                return query(head(node) , 1 , N , x ,y) ;
        }
        int mid = (L + R ) >> 1 ; 
        long long s1 = query2(Left(node ,1) , L , mid , l , r , x , y) ; 
        long long s2 = query2(Right(node , 1) , mid+1 ,R , l , r, x , y) ; 
        return f(s1 , s2) ; 
}


void update(int P, int Q, long long K)
{
        P ++ ; Q ++ ; 
        upd(0 , 1 , N , P , Q , K) ;
}

long long calculate(int P, int Q, int U, int V)
{
        P++ ; Q ++ ; U ++ ; V++ ; 
        return query2(0 , 1 , N , P , U , Q , V) ; 
}

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 Correct 11 ms 19840 KB Output is correct
2 Incorrect 11 ms 19968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19840 KB Output is correct
2 Incorrect 10 ms 19840 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19840 KB Output is correct
2 Incorrect 12 ms 19968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19840 KB Output is correct
2 Incorrect 11 ms 19968 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19840 KB Output is correct
2 Incorrect 11 ms 19968 KB Output isn't correct
3 Halted 0 ms 0 KB -