| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 551032 | tatyam | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using u64 = uint64_t;
u32 R, C;
struct DynamicSegTree{
unordered_map<u32, u64> seg;
u64 at(u32 x) const {
auto p = seg.find(x);
if(p == seg.end()) return 0;
return p->second;
}
void set(u32 i, u64 x){
i += C;
seg[i] = x;
while(i >= 2){
x = gcd(x, at(i ^ 1));
seg[i >>= 1] = x;
}
}
u64 get(u32 l, u32 r) const {
u64 ans = 0;
l += C;
r += C;
while(l < r){
if(l & 1) ans = gcd(ans, at(l++));
if(r & 1) ans = gcd(ans, at(--r));
l >>= 1;
r >>= 1;
}
return ans;
}
};
struct DynamicSegTree2D{
unordered_map<u32, DynamicSegTree> seg;
void set(u32 i, u32 j, u64 x){
i += R;
do seg[i].set(j, x); while(i >>= 1);
}
u64 get(u32 i, u32 y_l, u32 y_r) const {
auto p = seg.find(i);
if(p == seg.end()) return 0;
return p->second.get(y_l, y_r);
}
u64 get(u32 l, u32 r, u32 y_l, u32 y_r) const {
u64 ans = 0;
l += C;
r += C;
while(l < r){
if(l & 1) ans = gcd(ans, get(l++, y_l, y_r));
if(r & 1) ans = gcd(ans, get(--r, y_l, y_r));
l >>= 1;
r >>= 1;
}
return ans;
}
} seg;
void init(int R, int C){
::R = R;
::C = C;
}
void update(int P, int Q, long long K){
seg.set(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return seg.get(P, U + 1, Q, V + 1);
}