| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 640635 | SirCovidThe19th | 게임 (IOI13_game) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
template<class T> struct seg1d{
vector<T> seg{0, 0}; vector<int> lc{0, 0}, rc{0, 0};
int ext(int i){
if (i) return i;
seg.push_back(0); lc.push_back(0); rc.push_back(0);
return seg.size() - 1;
}
void upd(int pt, T v, int l = 0, int r = 1e9, int i = 1){
if (l == r){ seg[i] = v; return; }
int mid = (l + r) / 2;
if (pt <= mid) upd(pt, v, l, mid, lc[i] = ext(lc[i]));
else upd(pt, v, mid + 1, r, rc[i] = ext(rc[i]));
seg[i] = __gcd(seg[lc[i]], seg[rc[i]]);
}
T qry(int ql, int qr, int l = 0, int r = 1e9, int i = 1){
if (!i or r < ql or l > qr) return 0;
if (l >= ql and r <= qr) return seg[i];
int mid = (l + r) / 2;
return __gcd(qry(ql, qr, l, mid, lc[i]), qry(ql, qr, mid + 1, r, rc[i]));
}
};
template<class T> struct seg2d{
vector<seg1d<T>> seg{seg1d<T>(), seg1d<T>()}; vector<int> lc{0, 0}, rc{0, 0};
int ext(int i){
if (i) return i;
seg.push_back(seg1d<T>()); lc.push_back(0); rc.push_back(0);
return seg.size() - 1;
}
void upd(int ptX, int ptY, T v, int l = 0, int r = 1e9, int i = 1){
if (l == r){ seg[i].upd(ptY, __gcd(v, seg[i].qry(ptY, ptY))); return; }
int mid = (l + r) / 2;
if (ptX <= mid) upd(ptX, ptY, v, l, mid, lc[i] = ext(lc[i]));
else upd(ptX, ptY, v, mid + 1, r, rc[i] = ext(rc[i]));
seg[i].upd(ptY, __gcd(seg[lc[i]].qry(ptY, ptY), seg[rc[i]].qry(ptY, ptY)));
}
T qry(int qx1, int qy1, int qx2, int qy2, int l = 0, int r = 1e9, int i = 1){
if (!i or r < qx1 or l > qx2) return 0;
if (l >= qx1 and r <= qx2) return seg[i].qry(qy1, qy2);
int mid = (l + r) / 2;
return __gcd(qry(qx1, qy1, qx2, qy2, l, mid, lc[i]), qry(qx1, qy1, qx2, qy2, mid + 1, r, rc[i]));
}
};
seg2d<long long> ST;
void init(int r, int c){};
void update(int p, int q, long long k){ ST.upd(p, q, k); }
long long calculate(int p, int q, int u, int v){ return ST.qry(p, q, u, v); }