#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include "game.h"
#ifdef DEBUG
#include "debug.hpp"
#endif
using namespace std;
#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back
#ifdef DEBUG
#define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
#define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << " " << #x << " = " << x << endl; dbg::light = 0;}
#else
#define debug(x...)
#define light_debug(x)
#endif
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(1, 1 << 29);
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
class treap{
struct node{
int i, p;
ll v, g;
node* l; node* r;
node(int _i, ll _v){
i = _i, v = _v, g = _v;
l = r = 0;
p = uid(rng);
}
};
using pnode = node*;
pnode root = 0;
inline ll get_gcd(pnode t){
return t ? t->g : 0;
}
inline void pull(pnode t){
if(t) t->g = gcd2(gcd2(get_gcd(t->l), get_gcd(t->r)), t->v);
}
void split(pnode t, pnode& l, pnode& r, int i){
if(!t)
l = r = 0;
else if(t->i <= i)
split(t->r, t->r, r, i), l = t;
else
split(t->l, l, t->l, i), r = t;
pull(t);
}
void merge(pnode& t, pnode l, pnode r){
if(!l || !r)
t = l ? l : r;
else if(l->p > r->p)
merge(l->r, l->r, r), t = l;
else
merge(r->l, l, r->l), t = r;
pull(t);
}
public:
void update(int i, ll v){
pnode l, m, r;
split(root, m, r, i);
split(m, l, m, i - 1);
m = new node(i, v);
merge(root, l, m);
merge(root, root, r);
}
ll query(int s, int e){
pnode l, m, r;
split(root, l, m, s - 1);
split(m, m, r, e);
ll g = get_gcd(m);
merge(root, m, r);
merge(root, l, root);
return g;
}
};
class segtree{
struct node{
treap trp;
node *l = 0; node* r = 0;
};
using pnode = node*;
int R;
pnode root = 0;
void update(pnode& t, int s, int e, int p, int q, int v){
if(p < s || p > e)
return;
if(!t)
t = new node();
t->trp.update(q, v);
if(s != e)
update(t->l, s, (s + e) >> 1, p, q, v), update(t->r, (s + e + 2) >> 1, e, p, q, v);
}
ll query(pnode& t, int s, int e, int p, int q, int u, int v){
if(p > e || u < s || !t)
return 0;
if(p <= s && e <= u)
return t->trp.query(q, v);
return gcd2(query(t->l, s, (s + e) >> 1, p, q, u, v), query(t->r, (s + e) >> 1, e, p, q, u, v));
}
public:
segtree(int _R = 0){
R = _R;
}
inline void update(int p, int q, int v){
update(root, 0, R - 1, p, q, v);
}
inline ll query(int p, int q, int u, int v){
return query(root, 0, R - 1, p, q, u, v);
}
};
segtree seg;
void init(int R, int C) {
seg = segtree(R);
}
void update(int P, int Q, long long K) {
seg.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return seg.query(P, Q, U, V);
}
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;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
