#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k) for(int i = j ; i < k ; ++i)
#define RREP(i,j,k) for(int i = j ; i >=k ; --i)
#define A first
#define B second
#define mp make_pair
#define pb emplace_back
#define PII pair<int , int>
#define MEM(i,j) memset(i , j , sizeof i)
#define ALL(i) i.begin() , i.end()
#define DBGG(i,j) cout << i << " " << j << endl
#define DB4(i,j,k,l) cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
//------------------------------------------------------------
#include "game.h"
#define MAX 230000
#define INF 0x3f3f3f3f
#define mid ((l + r) >> 1)
long long n , m;
long long sum[MAX * 40];
int ls[MAX * 40] , rs[MAX * 40] , sec[MAX * 40] , pos = 2;
void init(int R, int C) {
n = R , m = C;
}
void update2(int now , int l , int r , int y , long long val){
assert(now != 0);
if(l == r) return sum[now] = val , void();
else {
if(y <= mid + 0){
if(ls[now] == 0) ls[now] = pos ++;
update2(ls[now] , l , mid + 0 , y , val);
}
if(mid + 1 <= y){
if(rs[now] == 0) rs[now] = pos ++;
update2(rs[now] , mid + 1 , r , y , val);
}
sum[now] = __gcd(sum[ls[now]] , sum[rs[now]]);
}
// DB4("now = " , sum[now] , sum[ls[now]] , sum[rs[now]]);
}
void update1(int now , int l , int r , int x , int y , long long val){
assert(now != 0);
if(sec[now] == 0) sec[now] = pos ++;
update2(sec[now] , 0 , m , y , val);
if(l == r);
else {
if(x <= mid + 0){
if(ls[now] == 0) ls[now] = pos ++;
update1(ls[now] , l , mid + 0 , x , y , val);
}
if(mid + 1 <= x){
if(rs[now] == 0) rs[now] = pos ++;
update1(rs[now] , mid + 1 , r , x , y , val);
}
}
}
void update(int P, int Q, long long K) {
if(pos == MAX * 38) assert(0);
update1(1 , 0 , n , P , Q , K);
}
long long query2(int now , int l , int r , int ql , int qr){
// DBGG("now = " , now);
if(now == 0) return 0;
if(ql <= l && r <= qr) return sum[now];
else if(qr <= mid + 0) return query2(ls[now] , l , mid + 0 , ql , qr);
else if(mid + 1 <= ql) return query2(rs[now] , mid + 1 , r , ql , qr);
else __gcd(query2(ls[now] , l , mid + 0 , ql , qr) , query2(rs[now] , mid + 1 , r , ql , qr));
}
long long query1(int now , int l , int r , int ql , int qr , int c , int d){
if(now == 0) return 0;
if(ql <= l && r <= qr) return query2(sec[now] , 0 , m , c , d);
else if(qr <= mid + 0) return query1(ls[now] , l , mid + 0 , ql , qr , c , d);
else if(mid + 1 <= ql) return query1(rs[now] , mid + 1 , r , ql , qr , c , d);
return __gcd(query1(ls[now] , l , mid + 0 , ql , qr , c , d)
, query1(rs[now] , mid + 1 , r , ql , qr , c , d));
}
long long calculate(int P, int Q, int U, int V) {
// DB4(P , Q , U , V);
// return 42;
return query1(1 , 0 , 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;
^~~
game.cpp: In function 'long long int query2(int, int, int, int, int)':
game.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
484 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
484 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
508 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
544 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
620 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
4 ms |
636 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
636 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
