#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll gcd2(ll a, ll b) {
if (b == 0) return a;
return gcd2(b, a % b);
}
struct Treap {
private:
struct Node {
pii key;
int prior;
ll val, gcd;
Node *l, *r;
Node(pii key, int val) : key(key), prior(rand()), val(val), gcd(val), l(nullptr), r(nullptr) {}
};
private:
typedef struct Node* pnode;
private:
pnode root;
void clear(pnode t) {
if (t) {
clear(t->l);
clear(t->r);
delete t;
}
}
ll gcd(pnode t) {
return t ? t->gcd : 0;
}
void upd(pnode t) {
if (t) {
t->gcd = gcd2(gcd(t->l), gcd(t->r));
t->gcd = gcd2(t->gcd, t->val);
}
}
void split(pnode t, pnode &l, pnode &r, pii key) {
if (!t) {
l = r = nullptr;
}
else if (t->key <= key) {
split(t->r, t->r, r, key), l = t;
}
else {
split(t->l, l, t->l, key), r = t;
}
upd(t);
}
void merge(pnode &t, pnode l, pnode r) {
if (!l || !r) {
t = l ? l : r;
}
else if (l->prior > r->prior) {
merge(l->r, l->r, r), t = l;
}
else {
merge(r->l, l, r->l), t = r;
}
upd(t);
}
pnode find(pnode t, pii key) {
if (!t) {
return nullptr;
}
if (t->key == key) {
return t;
}
if (t->key < key) {
return find(t->r, key);
}
else {
return find(t->l, key);
}
}
void updPath(pnode t, pii key) {
if (!t) {
return;
}
if (t->key == key) {
}
else if (t->key < key) {
updPath(t->r, key);
}
else {
updPath(t->l, key);
}
upd(t);
}
void insert(pnode &t, pnode it) {
if (!t) {
t = it;
}
else if (it->prior > t->prior) {
split(t, it->l, it->r, it->key), t = it;
}
else {
insert(t->key < it->key ? t->r : t->l, it);
}
upd(t);
}
ll gcdQuery(pnode t, int left, int right) {
pnode l, m, r;
split(t, m, r, {right + 1, -1});
split(m, l, m, {left, -1});
ll toReturn = m ? m->gcd : 0;
merge(t, l, m);
merge(t, t, r);
return toReturn;
}
public:
Treap() : root(nullptr) {
srand(time(nullptr));
}
~Treap() {
clear(this->root);
}
void smartInsert(pii key, ll val) {
pnode found = find(this->root, key);
if (found) {
found->val = val;
updPath(this->root, key);
}
else {
insert(this->root, new Node(key, val));
}
}
ll gcdQuery(int left, int right) {
return gcdQuery(this->root, left, right);
}
};
struct Segment {
private:
struct Node {
Treap treap;
Node *l, *r;
Node() : treap(Treap()), l(nullptr), r(nullptr) {}
};
private:
typedef struct Node* pnode;
private:
pnode root;
void clear(pnode t) {
if (t) {
clear(t->l);
clear(t->r);
delete t;
}
}
void update(pnode &t, int x, int y, int l, int r, ll val) {
if (!t) t = new Node();
t->treap.smartInsert({y, x}, val);
if (l == r) return;
int mid = (l + r) >> 1;
if (x <= mid) {
update(t->l, x, y, l, mid, val);
}
else {
update(t->r, x, y, mid + 1, r, val);
}
}
ll query(pnode t, int lx, int ly, int rx, int ry, int l, int r) {
if (!t) return 0;
if (l > rx || r < lx) return 0;
if (lx <= l && r <= rx) {
return t->treap.gcdQuery(ly, ry);
}
int mid = (l + r) >> 1;
ll ql = query(t->l, lx, ly, rx, ry, l, mid);
ll qr = query(t->r, lx, ly, rx, ry, mid + 1, r);
return gcd2(ql, qr);
}
public:
Segment() : root(nullptr) {
srand(time(nullptr));
}
~Segment() {
clear(this->root);
}
void update(int x, int y, int val) {
update(this->root, x, y, 0, 1e9, val);
}
ll query(int lx, int ly, int rx, int ry) {
return query(this->root, lx, ly, rx, ry, 0, 1e9);
}
};
Segment tree;
void init(int R, int C) {
}
void update(int P, int Q, ll K) {
tree.update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return tree.query(P, Q, U, V);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
