# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
962798 |
2024-04-14T08:24:09 Z |
danikoynov |
Game (IOI13_game) |
C++14 |
|
0 ms |
0 KB |
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
void init(int R, int C)
{
/* ... */
}
const ll inf = 1e18;
const int maxc = 1e9 + 10;
vector < pair < int, ll > > keys;
mt19937 rng;
struct node
{
int priority, sz;
ll sub;
pair < int, ll > key;
node *lc, *rc;
node(pair < int, ll > _key = {0, 0})
{
key = _key;
priority = rng();
sz = 1;
lc = rc = NULL;
}
void con()
{
sz = 1;
sub = key.second;
if (lc != NULL)
{
sz += lc -> sz;
sub = gcd2(sub, lc -> sub);
}
if (rc != NULL)
{
sz += rc -> sz;
sub = gcd2(sub, rc -> sub);
}
}
void print()
{
if (lc) lc -> print();
cout << key.first << " " << key.second << endl;
if (rc) rc -> print();
}
void get_keys()
{
if (lc) lc -> get_keys();
keys.insert(key);
if (rc) rc -> get_keys();
}
};
struct Treap
{
node *root = NULL;
void SplitKey(node *T, node *&L, node *&R, pair < int, ll > splitter)
{
if (T == NULL)
{
L = NULL;
R = NULL;
return;
}
if (T -> key < splitter)
{
L = T;
SplitKey(T -> rc, L -> rc, R, splitter);
}
else
{
R = T;
SplitKey(T -> lc, L, R -> lc, splitter);
}
T -> con();
}
void SplitSize(node *T, node *&L, node *&R, int tsz)
{
if (T == NULL)
{
L = NULL;
R = NULL;
return;
}
int csz = 1;
if (T -> lc) csz += T -> lc -> sz;
if (tsz >= csz)
{
L = T;
SplitSize(T -> rc, L -> rc, R, tsz - csz);
}
else
{
R = T;
SplitSize(T -> lc, L, R -> lc, tsz);
}
T -> con();
}
void Merge(node *&T, node *L, node *R)
{
if (L == NULL)
{
T = R;
return;
}
if (R == NULL)
{
T = L;
return;
}
if (L -> priority > R -> priority)
{
T = L;
Merge(T -> rc, L -> rc, R);
}
else
{
T = R;
Merge(T -> lc, L, R -> lc);
}
T -> con();
}
void add(pair < int, ll > cur)
{
node *L = NULL, *M = new node(cur), *R = NULL;
SplitKey(root, L, R, cur);
Merge(L, L, M);
Merge(root, L, R);
}
void rem(pair < int, ll > cur)
{
node *L = NULL, *R = NULL, *M = NULL;
SplitKey(root, L, R, cur);
SplitSize(R, M, R, 1);
Merge(root, L, R);
}
ll query(int l, int r)
{
node *L, *M, *R;
SplitKey(root, L, R, {l, -inf});
SplitKey(R, M, R, {r + 1, -inf});
ll res = 0;
if (M != NULL) res = M -> sub;
Merge(R, M, R);
Merge(root, L, R);
return res;
}
void print()
{
cout << "My Treap" << endl;
root -> print();
cout << "------------" << endl;
}
//void get_key()
};
struct vertex
{
vertex *lc, *rc;
multiset < pair < int, ll > > values;
Treap buzz;
vertex()
{
lc = rc = NULL;
values.clear();
}
};
vertex *tree = new vertex();
void make_kids(vertex *root)
{
if (root -> lc == NULL)
root -> lc = new vertex();
if (root -> rc == NULL)
root -> rc = new vertex();
}
void add_to_vertex(vertex *root, pair < int, ll > val)
{
root -> values.insert(val);
root -> buzz.add(val);
int sz = 0;
if (root -> buzz.root != NULL) sz = root -> buzz.root -> sz;
assert(sz == root -> values.size());
//assert(root -> buzz.root -> sz == root -> values.size());
}
void remove_from_vertex(vertex *root, pair < int, ll > val)
{
//cout << "remove " << " " << val.first << " " << val.second << endl;
//root -> buzz.print();
/**cout << "my set" << endl;
for (pair < int, ll > cur : root ->values)
cout << cur.first << " " << cur.second << endl;*/
root -> buzz.rem(val);
root -> values.erase(root -> values.find(val));
/**cout << "after" << endl;
root -> buzz.print();
cout << "the set" << endl;
for (pair < int, ll > cur : root ->values)
cout << cur.first << " " << cur.second << endl;*/
int sz = 0;
if (root -> buzz.root != NULL) sz = root -> buzz.root -> sz;
assert(sz == root -> values.size());
}
void add_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
///cout << "add val " << left << " " << right << " " << pivot << endl;
add_to_vertex(root, val);
///cout << "fine" << endl;
if (left == right)
return;
make_kids(root);
int mid = (left + right) / 2;
if (pivot <= mid)
add_val(root -> lc, left, mid, pivot, val);
else
add_val(root -> rc, mid + 1, right, pivot, val);
}
void remove_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
remove_from_vertex(root, val);
if (left == right)
return;
///make_kids(root);
int mid = (left + right) / 2;
if (pivot <= mid)
remove_val(root -> lc, left, mid, pivot, val);
else
remove_val(root -> rc, mid + 1, right, pivot, val);
}
map < pair < int, int >, ll > board;
void update(int P, int Q, long long K)
{
//cout << "update " << P << " " << Q << " " << K << endl;
if (board.count({P, Q}))
remove_val(tree, 0, maxc, P, {Q, board[{P, Q}]});
// cout << "Survive" << endl;
board[{P, Q}] = K;
add_val(tree, 0, maxc, P, {Q, K});
///cout << "Fuck" << endl;
/* ... */
}
ll query_vertex(vertex *root, int dw, int up)
{
ll res = 0;
//ll res = root -> buzz.query(dw, up);
for (pair < int, ll > cur : root -> values)
{
if (cur.first >= dw && cur.first <= up)
res = gcd2(res, cur.second);
}
return res;
}
ll query(vertex *root, int left, int right, int qleft, int qright, int kmin, int kmax)
{
if (root == NULL || left > qright || right < qleft)
return 0;
if (left >= qleft && right <= qright)
{
return query_vertex(root, kmin, kmax);
}
int mid = (left + right) / 2;
return gcd2(query(root -> lc, left, mid, qleft, qright, kmin, kmax),
query(root -> rc, mid + 1, right, qleft, qright, kmin, kmax));
}
long long calculate(int P, int Q, int U, int V)
{
/**map < pair < int, int >, ll > :: iterator it;
ll res = 0;
for (it = board.begin(); it != board.end(); it ++)
{
pair < int, int > cor = it -> first;
if (cor.first >= P && cor.first <= U &&
cor.second >= Q && cor.second <= V)
{
res = __gcd(res, it -> second);
}
}*/
/* ... */
return query(tree, 0, maxc, P, U, Q, V);
}
Compilation message
game.cpp: In member function 'void node::get_keys()':
game.cpp:75:26: error: no matching function for call to 'std::vector<std::pair<int, long long int> >::insert(std::pair<int, long long int>&)'
75 | keys.insert(key);
| ^
In file included from /usr/include/c++/10/vector:72,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from game.cpp:3:
/usr/include/c++/10/bits/vector.tcc:130:5: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, const value_type&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, long long int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, long long int> >::const_iterator; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
130 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/vector.tcc:130:5: note: candidate expects 2 arguments, 1 provided
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/queue:61,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
from game.cpp:3:
/usr/include/c++/10/bits/stl_vector.h:1293:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, long long int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, long long int> >::const_iterator; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
1293 | insert(const_iterator __position, value_type&& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1293:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_vector.h:1310:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::initializer_list<_Tp>) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, long long int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, long long int> >::const_iterator]'
1310 | insert(const_iterator __position, initializer_list<value_type> __l)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1310:7: note: candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_vector.h:1335:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::size_type, const value_type&) [with _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >; std::vector<_Tp, _Alloc>::iterator = std::vector<std::pair<int, long long int> >::iterator; std::vector<_Tp, _Alloc>::const_iterator = std::vector<std::pair<int, long long int> >::const_iterator; std::vector<_Tp, _Alloc>::size_type = long unsigned int; std::vector<_Tp, _Alloc>::value_type = std::pair<int, long long int>]'
1335 | insert(const_iterator __position, size_type __n, const value_type& __x)
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1335:7: note: candidate expects 3 arguments, 1 provided
/usr/include/c++/10/bits/stl_vector.h:1379:2: note: candidate: 'template<class _InputIterator, class> std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::insert(std::vector<_Tp, _Alloc>::const_iterator, _InputIterator, _InputIterator) [with _InputIterator = _InputIterator; <template-parameter-2-2> = <template-parameter-1-2>; _Tp = std::pair<int, long long int>; _Alloc = std::allocator<std::pair<int, long long int> >]'
1379 | insert(const_iterator __position, _InputIterator __first,
| ^~~~~~
/usr/include/c++/10/bits/stl_vector.h:1379:2: note: template argument deduction/substitution failed:
game.cpp:75:26: note: candidate expects 3 arguments, 1 provided
75 | keys.insert(key);
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from game.cpp:3:
game.cpp: In function 'void add_to_vertex(vertex*, std::pair<int, long long int>)':
game.cpp:228:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
228 | assert(sz == root -> values.size());
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void remove_from_vertex(vertex*, std::pair<int, long long int>)':
game.cpp:249:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::multiset<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | assert(sz == root -> values.size());
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void add_val(vertex*, int, int, int, std::pair<int, long long int>)':
game.cpp:256:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
256 | if (left == right)
| ^~
game.cpp:259:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
259 | make_kids(root);
| ^~~~~~~~~