# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
739693 |
2023-05-11T04:11:52 Z |
scanhex |
Game (IOI13_game) |
C++17 |
|
7289 ms |
256000 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long nagai;
#include "game.h"
//pizda
template<typename T>
class fake_ptr {
private:
uint32_t null = -1;
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() : arr_ind{null} {}
explicit fake_ptr(uint32_t arr_ind) : arr_ind{arr_ind} {};
T* operator ->() {
assert(arr_ind != null);
return &mem()[arr_ind];
}
fake_ptr& operator=(const fake_ptr& o) {
arr_ind = o.arr_ind;
return *this;
}
operator bool() {
return arr_ind != null;
}
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 = 1000000010;
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:102:3: required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:195:27: required from here
game.cpp:87: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]
87 | 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:111:16: required from 'void sl<H>::insert(std::pair<int, int>, nagai) [with int H = 18; nagai = long long int]'
game.cpp:195:27: required from here
game.cpp:95:13: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
95 | while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
| ~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
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 |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
296 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
300 KB |
Output is correct |
4 |
Correct |
1025 ms |
11460 KB |
Output is correct |
5 |
Correct |
543 ms |
11620 KB |
Output is correct |
6 |
Correct |
757 ms |
8456 KB |
Output is correct |
7 |
Correct |
955 ms |
8212 KB |
Output is correct |
8 |
Correct |
512 ms |
5776 KB |
Output is correct |
9 |
Correct |
878 ms |
8276 KB |
Output is correct |
10 |
Correct |
872 ms |
7960 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
424 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 |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
0 ms |
296 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 |
432 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2273 ms |
21216 KB |
Output is correct |
13 |
Correct |
3981 ms |
17732 KB |
Output is correct |
14 |
Correct |
824 ms |
17280 KB |
Output is correct |
15 |
Correct |
4310 ms |
20240 KB |
Output is correct |
16 |
Correct |
422 ms |
20372 KB |
Output is correct |
17 |
Correct |
1581 ms |
12636 KB |
Output is correct |
18 |
Correct |
3612 ms |
20688 KB |
Output is correct |
19 |
Correct |
2704 ms |
20872 KB |
Output is correct |
20 |
Correct |
2808 ms |
20208 KB |
Output is correct |
21 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
300 KB |
Output is correct |
2 |
Correct |
2 ms |
432 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
1 ms |
304 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 |
296 KB |
Output is correct |
12 |
Correct |
994 ms |
11432 KB |
Output is correct |
13 |
Correct |
579 ms |
11684 KB |
Output is correct |
14 |
Correct |
750 ms |
8412 KB |
Output is correct |
15 |
Correct |
1067 ms |
8128 KB |
Output is correct |
16 |
Correct |
551 ms |
5692 KB |
Output is correct |
17 |
Correct |
1045 ms |
8204 KB |
Output is correct |
18 |
Correct |
1032 ms |
7960 KB |
Output is correct |
19 |
Correct |
2580 ms |
21172 KB |
Output is correct |
20 |
Correct |
4507 ms |
17636 KB |
Output is correct |
21 |
Correct |
824 ms |
17368 KB |
Output is correct |
22 |
Correct |
4381 ms |
20120 KB |
Output is correct |
23 |
Correct |
459 ms |
20284 KB |
Output is correct |
24 |
Correct |
1604 ms |
12660 KB |
Output is correct |
25 |
Correct |
3628 ms |
20792 KB |
Output is correct |
26 |
Correct |
2691 ms |
21052 KB |
Output is correct |
27 |
Correct |
2781 ms |
20476 KB |
Output is correct |
28 |
Correct |
1887 ms |
249728 KB |
Output is correct |
29 |
Correct |
3613 ms |
252600 KB |
Output is correct |
30 |
Correct |
7287 ms |
156020 KB |
Output is correct |
31 |
Correct |
6605 ms |
130096 KB |
Output is correct |
32 |
Correct |
1444 ms |
49412 KB |
Output is correct |
33 |
Correct |
1928 ms |
50984 KB |
Output is correct |
34 |
Correct |
812 ms |
249356 KB |
Output is correct |
35 |
Correct |
2315 ms |
130784 KB |
Output is correct |
36 |
Correct |
5523 ms |
249752 KB |
Output is correct |
37 |
Correct |
3974 ms |
249976 KB |
Output is correct |
38 |
Correct |
4145 ms |
249532 KB |
Output is correct |
39 |
Correct |
3147 ms |
194404 KB |
Output is correct |
40 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
296 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 |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
2 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
304 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 |
384 KB |
Output is correct |
12 |
Correct |
961 ms |
11476 KB |
Output is correct |
13 |
Correct |
512 ms |
11868 KB |
Output is correct |
14 |
Correct |
752 ms |
8480 KB |
Output is correct |
15 |
Correct |
882 ms |
8264 KB |
Output is correct |
16 |
Correct |
495 ms |
5832 KB |
Output is correct |
17 |
Correct |
843 ms |
8420 KB |
Output is correct |
18 |
Correct |
883 ms |
8008 KB |
Output is correct |
19 |
Correct |
2246 ms |
21492 KB |
Output is correct |
20 |
Correct |
3898 ms |
18052 KB |
Output is correct |
21 |
Correct |
845 ms |
17432 KB |
Output is correct |
22 |
Correct |
4294 ms |
20404 KB |
Output is correct |
23 |
Correct |
410 ms |
20492 KB |
Output is correct |
24 |
Correct |
1517 ms |
12772 KB |
Output is correct |
25 |
Correct |
3566 ms |
20956 KB |
Output is correct |
26 |
Correct |
2751 ms |
21192 KB |
Output is correct |
27 |
Correct |
2701 ms |
20532 KB |
Output is correct |
28 |
Correct |
1861 ms |
249504 KB |
Output is correct |
29 |
Correct |
3689 ms |
252540 KB |
Output is correct |
30 |
Correct |
7289 ms |
155760 KB |
Output is correct |
31 |
Correct |
6558 ms |
129576 KB |
Output is correct |
32 |
Correct |
1440 ms |
48880 KB |
Output is correct |
33 |
Correct |
1948 ms |
50552 KB |
Output is correct |
34 |
Correct |
811 ms |
248892 KB |
Output is correct |
35 |
Correct |
2807 ms |
130188 KB |
Output is correct |
36 |
Correct |
5862 ms |
249420 KB |
Output is correct |
37 |
Correct |
4439 ms |
249552 KB |
Output is correct |
38 |
Correct |
4867 ms |
248892 KB |
Output is correct |
39 |
Runtime error |
883 ms |
256000 KB |
Execution killed with signal 9 |
40 |
Halted |
0 ms |
0 KB |
- |