| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 63776 | mohammad_kilani | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
map < pair<int,int> , long long > mp;
int r1 , r2 , c1 , c2 , F ,r , c ;
long long val;
long long update_cols(int s,int e,int idx){
if(s > c1 || e < c1){
if(mp.find(make_pair(F,idx)) == mp.end())
return 0;
return mp[make_pair(F,idx)];
}
if(s == e){
return mp[make_pair(F,idx)] = val;
}
return mp[make_pair(F,idx)] = gcd2(update_cols(s,((s+e) >> 1),(idx << 1)),update_cols(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
void update_rows(int s,int e,int idx){
if(s > r1 || e < r1)
return;
if(s == e){
F = idx;
update_cols(0 , c , 1);
return;
}
update_rows(s,((s+e) >> 1),(idx << 1));
update_rows(((s+e) >> 1) + 1, e, (idx << 1) + 1);
F = idx;
update_cols(0 , c , 1);
}
long long get_cols(int s,int e,int idx){
if(s > c2 || e < c1 || mp.find(make_pair(F,idx)) == mp.end())
return 0;
if(s >= c1 && e <= c2)
return mp[make_pair(F,idx)];
return gcd2(get_cols(s,((s+e) >> 1),(idx << 1)),get_cols(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
long long get_rows(int s,int e,int idx){
if(s > r2 || e < r1)
return 0;
if(s >= r1 && e <= r2){
F = idx;
return get_cols(0 , c , 1);
}
return gcd2(get_rows(s,((s+e) >> 1),(idx << 1)),get_rows(((s+e) >> 1) + 1, e, (idx << 1) + 1));
}
void init(int R, int C) {
r = R ;
c = C;
}
void update(int P, int Q, long long K) {
r1 = P;
c1 = Q;
val = K;
update_rows(0 , r , 1);
}
long long calculate(int P, int Q, int U, int V) {
r1 = P;
r2 = U;
c1 = Q;
c2 = V;
return get_rows(0 , r , 1);
}