oj.uz

Submission #237830

# Submission time Handle Problem Language Result Execution time Memory
237830 2020-06-09T00:33:10 Z mohamedsobhi777 Game (IOI13_game) C++14
37 / 100
 13000 ms 69368 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){
         //       cout<< node <<" " << L <<" " << R <<" " << ix <<" " << val <<"....\n"; 
                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) ;
        }
 
} ; 
vector<dynamic_segmentree> d ; 
 
int root[N] ; 
 
void update(int a , int b , long long c){
        b++ ; 
        if(root[a] == -1){
                root[a] = ++count_nodes ; 
        }
        d[a].update(root[a] , 1 , maxc , b ,c ) ;
}
 
long long calculate(int a , int b , int c , int e){
        long long ret = 0 ; 
        b++ ; e++ ;
        for(int i = a ; i<=c ;i++){
                ret = gcd2(ret , d[i].query(root[i] , 1, maxc , b , e)) ; 
        }
        return ret ; 
}
 
void init(int R, int C) {
        memset(root , -1 , sizeof root) ;
        memset(lc ,-1 , sizeof lc) ; 
        memset(rc , -1 , sizeof rc) ; 
        d.resize(R+10) ;
}

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 35 ms 63352 KB Output is correct
2 Correct 35 ms 63352 KB Output is correct
3 Correct 34 ms 63360 KB Output is correct
4 Correct 35 ms 63360 KB Output is correct
5 Correct 34 ms 63352 KB Output is correct
6 Correct 35 ms 63360 KB Output is correct
7 Correct 36 ms 63412 KB Output is correct
8 Correct 35 ms 63352 KB Output is correct
9 Correct 34 ms 63352 KB Output is correct
10 Correct 35 ms 63352 KB Output is correct
11 Correct 34 ms 63360 KB Output is correct
12 Correct 35 ms 63352 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63352 KB Output is correct
2 Correct 38 ms 63352 KB Output is correct
3 Correct 34 ms 63360 KB Output is correct
4 Correct 894 ms 68216 KB Output is correct
5 Correct 599 ms 69368 KB Output is correct
6 Correct 662 ms 66040 KB Output is correct
7 Correct 708 ms 65656 KB Output is correct
8 Correct 539 ms 66168 KB Output is correct
9 Correct 695 ms 66168 KB Output is correct
10 Correct 648 ms 65476 KB Output is correct
11 Correct 35 ms 63352 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 63360 KB Output is correct
2 Correct 35 ms 63360 KB Output is correct
3 Correct 35 ms 63352 KB Output is correct
4 Correct 34 ms 63488 KB Output is correct
5 Correct 35 ms 63316 KB Output is correct
6 Correct 35 ms 63360 KB Output is correct
7 Correct 34 ms 63360 KB Output is correct
8 Correct 35 ms 63352 KB Output is correct
9 Correct 34 ms 63352 KB Output is correct
10 Correct 34 ms 63352 KB Output is correct
11 Correct 34 ms 63360 KB Output is correct
12 Execution timed out 13081 ms 65560 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63360 KB Output is correct
2 Correct 35 ms 63352 KB Output is correct
3 Correct 34 ms 63360 KB Output is correct
4 Correct 35 ms 63352 KB Output is correct
5 Correct 35 ms 63360 KB Output is correct
6 Correct 34 ms 63352 KB Output is correct
7 Correct 35 ms 63352 KB Output is correct
8 Correct 34 ms 63352 KB Output is correct
9 Correct 37 ms 63360 KB Output is correct
10 Correct 35 ms 63360 KB Output is correct
11 Correct 36 ms 63360 KB Output is correct
12 Correct 924 ms 68092 KB Output is correct
13 Correct 596 ms 69224 KB Output is correct
14 Correct 665 ms 66040 KB Output is correct
15 Correct 735 ms 65656 KB Output is correct
16 Correct 543 ms 66296 KB Output is correct
17 Correct 712 ms 65912 KB Output is correct
18 Correct 637 ms 65504 KB Output is correct
19 Execution timed out 13085 ms 66500 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 63360 KB Output is correct
2 Correct 35 ms 63336 KB Output is correct
3 Correct 35 ms 63360 KB Output is correct
4 Correct 35 ms 63352 KB Output is correct
5 Correct 36 ms 63360 KB Output is correct
6 Correct 35 ms 63352 KB Output is correct
7 Correct 34 ms 63352 KB Output is correct
8 Correct 35 ms 63352 KB Output is correct
9 Correct 35 ms 63360 KB Output is correct
10 Correct 35 ms 63352 KB Output is correct
11 Correct 36 ms 63352 KB Output is correct
12 Correct 881 ms 68204 KB Output is correct
13 Correct 600 ms 69368 KB Output is correct
14 Correct 667 ms 66216 KB Output is correct
15 Correct 721 ms 65656 KB Output is correct
16 Correct 538 ms 66552 KB Output is correct
17 Correct 689 ms 65784 KB Output is correct
18 Correct 638 ms 65272 KB Output is correct
19 Execution timed out 13060 ms 66548 KB Time limit exceeded
20 Halted 0 ms 0 KB -