| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 437357 | Eric_hoo | 웜뱃 (IOI13_wombats) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define W(x) ((x) ? (x)->w : 0)
#define ID(x, y) (((long long)(x) << 30) + (y))
using namespace std;
inline long long gcd(long long x, long long y) {
while (x && y) {
if (x > y) x = x % y;
else y = y % x;
}
return x | y;
}
struct Node {
long long x; long long y, w; int fix;
Node *lson, *rson;
Node() {fix = rand(), lson = rson = NULL;}
void pushup() {w = gcd(y, gcd(W(lson), W(rson)));}
}NODEPOOL[700000], *NODECUR = NODEPOOL;
Node *merge(Node *l, Node *r) {
if (!l || !r) return l ? l : r;
if (l->fix > r->fix) {
l->rson = merge(l->rson, r);
l->pushup();
return l;
} else {
r->lson = merge(l, r->lson);
r->pushup();
return r;
}
}
void split(Node *T, long long x, Node *&l, Node *&r) {
if (!T) {l = r = NULL; return ;}
if (x < T->x) split(T->lson, x, l, r), T->lson = r, T->pushup(), r = T;
else split(T->rson, x, l, r), T->rson = l, T->pushup(), l = T;
}
void Insert(Node *&T, int x, int y, long long w) {
Node *t1, *t2, *t3;
split(T, ID(y, x - 1), t1, t2), split(t2, ID(y, x), t2, t3);
if (!t2) t2 = NODECUR++;
t2->x = ID(y, x), t2->y = t2->w = w;
T = merge(t1, merge(t2, t3));
}
long long Query(Node *T, int l, int r) {
Node *t1, *t2, *t3;
split(T, ID(l, -1), t1, t2), split(t2, ID(r + 1, -1), t2, t3);
long long ans = W(t2);
T = merge(t1, merge(t2, t3));
return ans;
}
struct Seg {
Node *T;
Seg *lson, *rson;
Seg() {T = NULL, lson = rson = NULL;}
}SEGPOOL[700000], *SEGCUR = SEGPOOL, *T = NULL;
void Update(Seg *&T, int l, int r, int x, int y, long long w) {
if (!T) T = SEGCUR++;
Insert(T->T, x, y, w);
if (l == r) return ;
int mid = l + r >> 1;
if (x <= mid) Update(T->lson, l, mid, x, y, w);
else Update(T->rson, mid + 1, r, x, y, w);
}
long long Query(Seg *T, int l, int r, int L, int R, int LL, int RR) {
if (!T) return 0;
if (l == L && r == R) return Query(T->T, LL, RR);
int mid = l + r >> 1;
if (R <= mid) return Query(T->lson, l, mid, L, R, LL, RR);
if (L > mid) return Query(T->rson, mid + 1, r, L, R, LL, RR);
return gcd(Query(T->lson, l, mid, L, mid, LL, RR), Query(T->rson, mid + 1, r, mid + 1, R, LL, RR));
}
int N, M, Q;
void read(int &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
void read(long long &x) {
char c = getchar(); while (c < '0' || c > '9') c = getchar();
x = c - '0', c = getchar(); while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
}
char st[100];
void print(long long x) {
int tp = 0;
if (!x) st[tp++] = '0';
while (x) st[tp++] = x % 10 + '0', x /= 10;
while (tp--) putchar(st[tp]);
putchar('\n');
}
void init(int R, int C) {
N = R, M = C, srand(2333);
}
void update(int x1, int y1, long long w) {
x1++, y1++;
Update(T, 1, N, x1, y1, w);
}
long long calculate(int x1, int x2, int y1, int y2) {
x1++, x2++, y1++, y2++;
return Query(T, 1, N, x1, y1, x2, y2);
}