# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
962784 |
2024-04-14T08:12:34 Z |
danikoynov |
Game (IOI13_game) |
C++14 |
|
3 ms |
604 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);
}
}
};
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;
}
};
struct vertex
{
vertex *lc, *rc;
set < 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);
}
void remove_from_vertex(vertex *root, pair < int, ll > val)
{
root -> buzz.rem(val);
//root -> values.erase(val);
}
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 = 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 function 'void add_val(vertex*, int, int, int, std::pair<int, long long int>)':
game.cpp:212:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
212 | if (left == right)
| ^~
game.cpp:215:11: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
215 | make_kids(root);
| ^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
3 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
3 ms |
604 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |