| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 962794 |
2024-04-14T08:22:14 Z |
danikoynov |
Game (IOI13_game) |
C++14 |
|
13000 ms |
30104 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;
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();
}
};
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;
}
};
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);
//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
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 remove_from_vertex(vertex*, std::pair<int, long long int>)':
game.cpp:234: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]
234 | assert(sz == root -> values.size());
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~
game.cpp: In function 'void add_val(vertex*, int, int, int, std::pair<int, long long int>)':
game.cpp:241:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
241 | if (left == right)
| ^~
game.cpp:244:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
244 | make_kids(root);
| ^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
1 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
856 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
13078 ms |
30104 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
604 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
604 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Execution timed out |
13086 ms |
27724 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
828 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
1 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
604 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Execution timed out |
13025 ms |
29456 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
3 ms |
604 KB |
Output is correct |
| 3 |
Correct |
3 ms |
604 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Correct |
3 ms |
604 KB |
Output is correct |
| 7 |
Correct |
0 ms |
348 KB |
Output is correct |
| 8 |
Correct |
0 ms |
348 KB |
Output is correct |
| 9 |
Correct |
2 ms |
604 KB |
Output is correct |
| 10 |
Correct |
1 ms |
348 KB |
Output is correct |
| 11 |
Correct |
1 ms |
604 KB |
Output is correct |
| 12 |
Execution timed out |
13099 ms |
29620 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
