#include <bits/stdc++.h>
#include "game.h"
using namespace std;
template<class T, class U>
void ckmin(T &a, U b)
{
if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
if (a < b) a = b;
}
#define y1 qwertyuiop
#define y2 asdfghjkl
#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
int N, M;
ll gcd(ll a, ll b)
{
return (b == 0 ? a : gcd(b, a % b));
}
struct node
{
int idx, pri;
ll cur, stor;
node *ch[2];
node(int x, ll v)
{
idx = x; pri = (rand() << 15 + rand()) % INF;
cur = v; stor = v;
ch[0] = nullptr; ch[1] = nullptr;
}
};
void pull(node *t)
{
if (!t) return;
t -> stor = t -> cur;
if (t -> ch[0]) t -> stor = gcd(t -> stor, t -> ch[0] -> stor);
if (t -> ch[1]) t -> stor = gcd(t -> stor, t -> ch[1] -> stor);
return;
}
typedef pair<node*, node*> pnn;
node *merge(node *l, node *r)
{
if (!l) return r;
if (!r) return l;
if (l -> pri > r -> pri)
{
l -> ch[1] = merge(l -> ch[1], r);
pull(l); return l;
}
else
{
r -> ch[0] = merge(l, r -> ch[0]);
pull(r); return r;
}
}
pnn split(node *t, int v)
{
if (!t) return {t, t};
int cur = t -> idx;
if (v > cur)
{
pnn p = split(t -> ch[1], v);
t -> ch[1] = p.fi; pull(t);
return {t, p.se};
}
else
{
pnn p = split(t -> ch[0], v);
t -> ch[0] = p.se; pull(t);
return {p.fi, t};
}
}
void inorder(node *t)
{
if (!t) return;
inorder(t -> ch[0]);
cerr << t -> idx << ',' << t -> cur << ' ';
inorder(t -> ch[1]);
}
struct Node
{
node *root;
Node *ch[2];
Node()
{
root = nullptr;
ch[0] = nullptr;
ch[1] = nullptr;
}
};
Node *root;
Node* upd(Node *t, int L, int R, int a, int y, ll v)
{
if (!t) t = new Node();
pnn p = split(t -> root, y), p1 = split(p.se, y + 1);
t -> root = merge(p.fi, merge(new node(y, v), p1.se));
// cerr << "PUSH\n";
// cerr << L << " -> " << R << endl;
// inorder(t -> root);
// cerr << endl;
if (L != R)
{
int mid = (L + R) >> 1;
if (a <= mid)
{
t -> ch[0] = upd(t -> ch[0], L, mid, a, y, v);
}
else
{
t -> ch[1] = upd(t -> ch[1], mid + 1, R, a, y, v);
}
}
return t;
}
ll qry(Node *t, int L, int R, int a, int b, int y1, int y2)
{
// cerr << (t ? "YES" : "NO") << endl;
// cerr << "WORK " << y1 << ' ' << y2 << endl;
if (!t) return 0;
if (a <= L && R <= b)
{
// cerr << "PULL\n";
// cerr << L << " -> " << R << endl;
// inorder(t -> root);
// cerr << endl;
pnn p = split(t -> root, y1), p1 = split(p.se, y2 + 1);
// cerr << "SOLVE\n";
// cerr << L << " -> " << R << endl;
// inorder(p1.fi);
// cerr << endl;
ll res = (p1.fi ? p1.fi -> stor : 0);
t -> root = merge(p.fi, merge(p1.fi, p1.se));
return res;
}
int mid = (L + R) >> 1;
if (b <= mid) return qry(t -> ch[0], L, mid, a, b, y1, y2);
if (mid < a) return qry(t -> ch[1], mid + 1, R, a, b, y1, y2);
return gcd(qry(t -> ch[0], L, mid, a, b, y1, y2), qry(t -> ch[1], mid + 1, R, a, b, y1, y2));
}
void init(int n, int m)
{
N = n; M = m;
srand(69);
}
void update(int x, int y, ll v)
{
root = upd(root, 0, N - 1, x, y, v);
}
ll calculate(int x1, int y1, int x2, int y2)
{
// cerr << x1 << ' ' << x2 << ' ' << y1 << ' ' << y2 << endl;
return qry(root, 0, N - 1, x1, x2, y1, y2);
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
game.cpp: In constructor 'node::node(int, ll)':
game.cpp:55:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
idx = x; pri = (rand() << 15 + rand()) % INF;
~~~^~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
