#include<bits/stdc++.h>
#include "game.h"
#define maxc 1000
#define maxr 1000
using namespace std ;
const int N =1000000 + 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 ] , lc[N * 4 ] , rc[N * 4 ] ;
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[1] ;
int LC[N * 4] , RC[N*4] ;
int countsegs ;
int root[N * 4] ;
void sharp_update(int x , int y , long long val){
if(root[x] == -1)
root[x] = ++ count_nodes ;
d[0].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) ;
}
if(LC[node] == -1 || RC[node] == -1){
sharp_update(node , ix2 , val) ;
}
else{
sharp_update(node , ix2 , gcd2( d[0].query(LC[node] , 1 , maxc , ix2 , ix2),
d[0].query( root[RC[node]] , 1 , maxc , ix2 , ix2)
)) ;
}
}
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[0].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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
109944 KB |
Output is correct |
| 2 |
Incorrect |
61 ms |
109944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
109944 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
109944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
109944 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
109944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
109944 KB |
Output is correct |
| 2 |
Incorrect |
61 ms |
109944 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
109944 KB |
Output is correct |
| 2 |
Incorrect |
59 ms |
109916 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
