#include "game.h"
#include <random>
#include <utility>
#include <string.h>
using namespace std;
using ll = long long;
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;
}
struct treap {
treap *L, *R;
int key, pri;
ll val, res;
treap(int i, ll x): key(i), pri(rand()), val(x), res(x), L(nullptr), R(nullptr) {}
treap *join(treap *L, treap *R) {
this->L = L;
this->R = R;
res = gcd2(val, gcd2(L ? L->res : 0, R ? R->res : 0));
return this;
}
};
treap* merge(treap *L, treap *R) {
if (!L) return R;
if (!R) return L;
if (L->pri > R->pri) {
return L->join(L->L, merge(L->R, R));
} else {
return R->join(merge(L, R->L), R->R);
}
}
pair<treap*, treap*> split(treap *T, int x) {
if (!T) return {nullptr, nullptr};
if (x <= T->key) {
auto [LL, LR] = split(T->L, x);
return {LL, T->join(LR, T->R)};
} else {
auto [RL, RR] = split(T->R, x);
return {T->join(T->L, RL), RR};
}
}
treap* insert(treap *T, int i, ll x) {
auto [L, R] = split(T, i);
return merge(L, merge(new treap(i, x), R));
}
// incl - excl
ll query(treap *T, int l, int r) {
auto [L, R] = split(T, l);
auto [RL, RR] = split(R, r);
ll res = RL ? RL->res : 0;
T = merge(L, merge(RL, RR));
return res;
}
// sparse segment tree
struct node {
node *L, *R;
treap *val;
node(): L(nullptr), R(nullptr), val(nullptr) {}
};
struct segtree {
node *root;
int sz;
int ql, qr, qx, qy;
ll qk;
segtree() {}
segtree(int N) {
sz = 1;
while (sz < N) sz *= 2;
root = new node();
}
void push(node *nd) {
if (!nd->L) nd->L = new node();
if (!nd->R) nd->R = new node();
}
ll __query(node *nd, int nl, int nr) {
if (qr <= nl || nr <= ql || nd == nullptr) return 0;
if (ql <= nl && nr <= qr) return ::query(nd->val, qx, qy);
int nm = (nl+nr)/2;
return gcd2(__query(nd->L, nl, nm), __query(nd->R, nm, nr));
}
ll query(int l, int r, int x, int y) {
ql = l; qr = r; qx = x; qy = y;
return __query(root, 0, sz);
}
void __upd(node *nd, int nl, int nr) {
if (ql < nl || nr <= ql) return;
nd->val = insert(nd->val, qx, qk);
if (nl+1 == nr) return;
push(nd);
int nm = (nl+nr)/2;
__upd(nd->L, nl, nm);
__upd(nd->R, nm, nr);
}
void upd(int l, int x, ll k) {
ql = l; qx = x; qk = k;
__upd(root, 0, sz);
}
};
segtree seg;
void init(int R, int C) {
seg = segtree(R);
}
void update(int P, int Q, long long K) {
seg.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
// P, U: rows
// Q, V: columns
return seg.query(P, U+1, Q, V+1);
}
Compilation message
game.cpp: In constructor 'treap::treap(int, ll)':
game.cpp:22:13: warning: 'treap::res' will be initialized after [-Wreorder]
22 | ll val, res;
| ^~~
game.cpp:20:12: warning: 'treap* treap::L' [-Wreorder]
20 | treap *L, *R;
| ^
game.cpp:23:5: warning: when initialized here [-Wreorder]
23 | treap(int i, ll x): key(i), pri(rand()), val(x), res(x), L(nullptr), R(nullptr) {}
| ^~~~~
game.cpp: In function 'std::pair<treap*, treap*> split(treap*, int)':
game.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [LL, LR] = split(T->L, x);
| ^
game.cpp:48:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
48 | auto [RL, RR] = split(T->R, x);
| ^
game.cpp: In function 'treap* insert(treap*, int, ll)':
game.cpp:54:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
54 | auto [L, R] = split(T, i);
| ^
game.cpp: In function 'll query(treap*, int, int)':
game.cpp:60:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
60 | auto [L, R] = split(T, l);
| ^
game.cpp:61:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
61 | auto [RL, RR] = split(R, r);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
