#include <bits/stdc++.h>
using namespace std;
typedef long long nagai;
#include "game.h"
//pizda
template<typename T>
class fake_ptr {
public:
static vector<T>& mem() {
static vector<T> mem_;
return mem_;
}
static void reserve(int cnt) {
mem().reserve(cnt);
}
static fake_ptr make() {
mem().push_back({});
return fake_ptr{static_cast<uint32_t>(mem().size() - 1)};
}
fake_ptr(){}
explicit fake_ptr(uint32_t arr_ind) : arr_ind{arr_ind} {};
T* operator ->() {
assert(arr_ind);
return &mem()[*arr_ind];
}
fake_ptr& operator=(const fake_ptr& o) {
arr_ind = o.arr_ind;
return *this;
}
operator bool() {
return arr_ind.has_value();
}
std::optional<std::uint32_t> arr_ind;
};
//template<typename T>
//vector<T> fake_ptr<T>::mem = {};
template<typename T>
fake_ptr<T> make_fake() {
return fake_ptr<T>::make();
}
nagai gcd(nagai a, nagai b)
{
while (b)
a = a % b, swap(a, b);
return a;
}
template<int H>
struct sl
{
struct nd
{
vector<fake_ptr<nd>> ri;
vector<nagai> gcd;
// vector<int> len;
pair<int, int> x;
inline int sz()
{
return ri.size();
}
};
fake_ptr<nd> header;
sl() {
header = make_fake<nd>();
header->ri.resize(H, {});
header->gcd.resize(H, 0);
header->x = {-1, -1};
//header->len.resize(H, 0);
}
fake_ptr<nd> last[H];
int len[H];
void go(pair<int, int> to)
{
fake_ptr<nd> cur = header;
for (int i = H - 1; i >= 0; --i)
{
while (i < cur->ri.size() && cur->ri[i] && cur->ri[i]->x < to)
cur = cur->ri[i];
last[i] = cur;
}
}
inline nagai calc(fake_ptr<nd> a, fake_ptr<nd> b, int i)
{
nagai g = a->gcd[i];
while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
a = a->ri[i], g = gcd(g, a->gcd[i]);
//cerr << a->x << ' ' << (b ? b->x : -2) << ' ' << i << ' ' << g << endl;
return g;
}
void insert(pair<int, int> ind, nagai val)
{
go(ind);
fake_ptr<nd> nw = make_fake<nd>();
nw->x = ind;
for (int i = 0, add = 1; i < H; add &= rand(), ++i)
{
if (add)
{
if (i > 0)
{
nagai g = calc(last[i], nw, i - 1);
nagai g1 = calc(nw, last[i]->ri[i], i - 1);
//cerr << "kek " << g << ' ' << last[i]->x << ' ' << last[i]->gcd[i - 1] << endl;
last[i]->gcd[i] = g;
nw->gcd.push_back(g1);
}
else
nw->gcd.push_back(val);
nw->ri.push_back(last[i]->ri[i]);
last[i]->ri[i] = nw;
}
else
{
last[i]->gcd[i] = gcd(last[i]->gcd[i], val);
}
}
}
void erase(pair<int, int> ind)
{
go(ind);
for (int i = 0; i < H; ++i)
{
if (last[i]->ri[i] && last[i]->ri[i]->x == ind)
{
if (i)
last[i]->gcd[i] = calc(last[i], last[i]->ri[i]->ri[i], i - 1);
last[i]->ri[i] = last[i]->ri[i]->ri[i];
}
else
last[i]->gcd[i] = calc(last[i], last[i]->ri[i], i - 1);
}
}
void print()
{
for (int i = 0; i < H; ++i)
{
auto v = header;
while (v)
cerr << '{' << v->x.first << ',' << v->x.second << '}' << ',' << v->gcd[i] << ' ', v = v->ri[i];
cerr << endl;
}
}
nagai get(pair<int, int> l, pair<int, int> r)
{
nagai g = 0;
go(l);
fake_ptr<nd> kek = last[0]->ri[0];
if (!kek)
return 0;
//cerr << kek->x.first << ' ' << kek->x.second << endl;
for (int i = 0; i < H; ++i)
while (i < kek->sz() && i + 1 >= kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
for (int i = H - 1; i >= 0; --i)
while (i < kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
if (kek->x < r)
g = gcd(g, kek->gcd[0]);
return g;
}
};
struct nd
{
nd* le;
nd* ri;
sl<18> skip;
nd()
: le(nullptr), ri(nullptr)
{}
void children()
{
if (!le)
le = new nd();
if (!ri)
ri = new nd();
}
void add(int l, int r, int x, int y, nagai val, bool add)
{
if (l > x || r <= x)
return;
if (add)
skip.insert({y, x}, val);
else
skip.erase({y, x});
if (r - l == 1)
return;
children();
int m = (l + r) / 2;
le->add(l, m, x, y, val, add);
ri->add(m, r, x, y, val, add);
}
nagai get(int l, int r, int ql1, int qr1, int ql2, int qr2)
{
//skip.print();
if (l >= qr1 || ql1 >= r)
return 0;
if (ql1 <= l && r <= qr1)
return skip.get({ql2, ql1}, {qr2, ql1});
if (!le && !ri)
return 0;
int m = (l + r) / 2;
if (!le)
return ri->get(m, r, ql1, qr1, ql2, qr2);
if (!ri)
return le->get(l, m, ql1, qr1, ql2, qr2);
return gcd(le->get(l, m, ql1, qr1, ql2, qr2),
ri->get(m, r, ql1, qr1, ql2, qr2));
}
};
nd* rt = new nd;
int MX = 1000000000;
set<pair<int, int>> p;
void init(int R, int C)
{
MX = R;
}
void update(int x, int y, long long t)
{
if (p.count({x, y}))
rt->add(0, MX, x, y, t, 0);
rt->add(0, MX, x, y, t, 1);
p.insert({x, y});
}
long long calculate(int xl, int yl, int xr, int yr)
{
return rt->get(0, MX, xl, xr + 1, yl, yr + 1);
}
Compilation message
game.cpp: In instantiation of 'void sl<H>::go(std::pair<int, int>) [with int H = 18]':
game.cpp:100:3: required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:193:27: required from here
game.cpp:85:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<fake_ptr<sl<18>::nd>, std::allocator<fake_ptr<sl<18>::nd> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | while (i < cur->ri.size() && cur->ri[i] && cur->ri[i]->x < to)
| ~~^~~~~~~~~~~~~~~~
game.cpp: In instantiation of 'nagai sl<H>::calc(fake_ptr<sl<H>::nd>, fake_ptr<sl<H>::nd>, int) [with int H = 18; nagai = long long int]':
game.cpp:109:16: required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:193:27: required from here
game.cpp:93:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
93 | while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
| ~~~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
424 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1012 ms |
11760 KB |
Output is correct |
5 |
Correct |
576 ms |
11988 KB |
Output is correct |
6 |
Correct |
729 ms |
8928 KB |
Output is correct |
7 |
Correct |
895 ms |
8564 KB |
Output is correct |
8 |
Correct |
533 ms |
6184 KB |
Output is correct |
9 |
Correct |
862 ms |
8700 KB |
Output is correct |
10 |
Correct |
912 ms |
8408 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
300 KB |
Output is correct |
6 |
Correct |
2 ms |
436 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2633 ms |
21616 KB |
Output is correct |
13 |
Correct |
4056 ms |
18076 KB |
Output is correct |
14 |
Correct |
978 ms |
17804 KB |
Output is correct |
15 |
Correct |
4408 ms |
20684 KB |
Output is correct |
16 |
Correct |
437 ms |
20744 KB |
Output is correct |
17 |
Correct |
1630 ms |
12960 KB |
Output is correct |
18 |
Correct |
3594 ms |
21124 KB |
Output is correct |
19 |
Correct |
2823 ms |
21348 KB |
Output is correct |
20 |
Correct |
2771 ms |
20676 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
0 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
997 ms |
11972 KB |
Output is correct |
13 |
Correct |
580 ms |
12156 KB |
Output is correct |
14 |
Correct |
766 ms |
8920 KB |
Output is correct |
15 |
Correct |
930 ms |
8592 KB |
Output is correct |
16 |
Correct |
521 ms |
6220 KB |
Output is correct |
17 |
Correct |
891 ms |
8668 KB |
Output is correct |
18 |
Correct |
864 ms |
8288 KB |
Output is correct |
19 |
Correct |
2435 ms |
21560 KB |
Output is correct |
20 |
Correct |
4003 ms |
17992 KB |
Output is correct |
21 |
Correct |
1002 ms |
17644 KB |
Output is correct |
22 |
Correct |
4300 ms |
20712 KB |
Output is correct |
23 |
Correct |
448 ms |
20816 KB |
Output is correct |
24 |
Correct |
1602 ms |
13088 KB |
Output is correct |
25 |
Correct |
3644 ms |
21108 KB |
Output is correct |
26 |
Correct |
2794 ms |
21224 KB |
Output is correct |
27 |
Correct |
2726 ms |
20584 KB |
Output is correct |
28 |
Correct |
2079 ms |
251932 KB |
Output is correct |
29 |
Correct |
4032 ms |
256000 KB |
Output is correct |
30 |
Correct |
8630 ms |
162628 KB |
Output is correct |
31 |
Correct |
7818 ms |
136488 KB |
Output is correct |
32 |
Correct |
1945 ms |
50456 KB |
Output is correct |
33 |
Correct |
2470 ms |
52568 KB |
Output is correct |
34 |
Correct |
869 ms |
255484 KB |
Output is correct |
35 |
Correct |
2479 ms |
140068 KB |
Output is correct |
36 |
Correct |
5469 ms |
256000 KB |
Output is correct |
37 |
Correct |
4235 ms |
256000 KB |
Output is correct |
38 |
Correct |
4290 ms |
256000 KB |
Output is correct |
39 |
Correct |
3524 ms |
204272 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
428 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1014 ms |
11864 KB |
Output is correct |
13 |
Correct |
601 ms |
12020 KB |
Output is correct |
14 |
Correct |
765 ms |
8752 KB |
Output is correct |
15 |
Correct |
985 ms |
8576 KB |
Output is correct |
16 |
Correct |
535 ms |
6180 KB |
Output is correct |
17 |
Correct |
887 ms |
8580 KB |
Output is correct |
18 |
Correct |
892 ms |
8256 KB |
Output is correct |
19 |
Correct |
2419 ms |
21504 KB |
Output is correct |
20 |
Correct |
4218 ms |
18180 KB |
Output is correct |
21 |
Correct |
971 ms |
17640 KB |
Output is correct |
22 |
Correct |
4413 ms |
20584 KB |
Output is correct |
23 |
Correct |
481 ms |
20780 KB |
Output is correct |
24 |
Correct |
1648 ms |
12900 KB |
Output is correct |
25 |
Correct |
3638 ms |
21064 KB |
Output is correct |
26 |
Correct |
2839 ms |
21448 KB |
Output is correct |
27 |
Correct |
2823 ms |
20604 KB |
Output is correct |
28 |
Correct |
2005 ms |
252552 KB |
Output is correct |
29 |
Correct |
4019 ms |
256000 KB |
Output is correct |
30 |
Correct |
9322 ms |
162528 KB |
Output is correct |
31 |
Correct |
8388 ms |
136440 KB |
Output is correct |
32 |
Correct |
1929 ms |
50448 KB |
Output is correct |
33 |
Correct |
2501 ms |
52560 KB |
Output is correct |
34 |
Correct |
933 ms |
255456 KB |
Output is correct |
35 |
Correct |
2760 ms |
140092 KB |
Output is correct |
36 |
Correct |
6040 ms |
256000 KB |
Output is correct |
37 |
Correct |
4455 ms |
256000 KB |
Output is correct |
38 |
Correct |
4909 ms |
256000 KB |
Output is correct |
39 |
Runtime error |
1106 ms |
256000 KB |
Execution killed with signal 9 |
40 |
Halted |
0 ms |
0 KB |
- |