oj.uz

Submission #237820

# Submission time Handle Problem Language Result Execution time Memory
237820 2020-06-08T23:31:49 Z mohamedsobhi777 Game (IOI13_game) C++14
37 / 100
 13000 ms 96632 KB 
#include<bits/stdc++.h>
#include "game.h"


using namespace std ; 

const int N =10000 + 7 ;

int n; 

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;
}

struct dynamic_segmentree{

        int count ; 
        long long iden = 0 ; 
        vector<long long> tree ; 
        vector<int> lc , rc ; 

        void init(int _n){
                count = 0 ; 
                tree.resize(4*_n) ; 
                lc = vector<int> (4*_n , -1) ; 
                rc = vector<int> (4*_n , -1) ;
        }

        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 ; 
                        update(lc[node] , L , mid , ix , val) ; 
                }
                else{
                        if(rc[node] == -1)
                                rc[node] = ++count ; 
                        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 nn ; 

void update(int a , int b , long long c){
        b++ ; 
        d[a].update(0 , 1 , nn , 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(0 , 1, nn , b , e)) ; 
        }
        return ret ; 
}


void init(int R, int C) {
        d.resize(R+10) ;
        nn = C +10 ;
        for(int i = 0 ;i <=R+3 ; i++){
                d[i].init(nn) ; 
        }
}

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 5 ms 384 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 5 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 745 ms 96632 KB Output is correct
5 Correct 490 ms 96376 KB Output is correct
6 Correct 602 ms 93944 KB Output is correct
7 Correct 680 ms 93632 KB Output is correct
8 Correct 477 ms 94184 KB Output is correct
9 Correct 640 ms 93692 KB Output is correct
10 Correct 576 ms 93432 KB Output is correct
11 Correct 4 ms 384 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 751 ms 96504 KB Output is correct
13 Correct 481 ms 96376 KB Output is correct
14 Correct 616 ms 93816 KB Output is correct
15 Correct 684 ms 93576 KB Output is correct
16 Correct 482 ms 93944 KB Output is correct
17 Correct 649 ms 93560 KB Output is correct
18 Correct 586 ms 93304 KB Output is correct
19 Execution timed out 13060 ms 68840 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 640 KB Output is correct
9 Correct 5 ms 1024 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 5 ms 1024 KB Output is correct
12 Correct 769 ms 96504 KB Output is correct
13 Correct 495 ms 96504 KB Output is correct
14 Correct 600 ms 93816 KB Output is correct
15 Correct 674 ms 93724 KB Output is correct
16 Correct 478 ms 94072 KB Output is correct
17 Correct 643 ms 93688 KB Output is correct
18 Correct 579 ms 93464 KB Output is correct
19 Execution timed out 13060 ms 69220 KB Time limit exceeded
20 Halted 0 ms 0 KB -