# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
967332 |
2024-04-22T02:17:49 Z |
obokaman |
Game (IOI13_game) |
C++17 |
|
0 ms |
0 KB |
#include <iostream>
#include <vector>
#include <string>
#include "game.h"
using namespace std;
typedef long long ll;
struct Node {
Node *l, *r;
int x;
ll val;
int prio;
ll gcd;
};
struct RowNode {
RowNode *l, *r;
int x;
Node* row;
Node* thick_row;
int prio;
};
Node* row(RowNode* t) {
return t ? t->row : nullptr;
}
Node* thick_row(RowNode* t) {
return t ? t->thick_row : nullptr;
}
ll gcd(Node* t) {
return t ? t->gcd : -1;
}
ll val(Node* t) {
return t ? t->val : -1;
}
ll gcdrec(ll a, ll b) {
return a == 0 ? b : gcdrec(b%a, a);
}
ll gcd(ll a, ll b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
return gcdrec(a, b);
}
Node* init_node(int x, ll val) {
Node* t = new Node;
t->l = t->r = nullptr;
t->x = x;
t->val = t->gcd = val;
t->prio = rand();
return t;
}
void update(Node* t) {
if (t) {
t->gcd = gcd(gcd(gcd(t->l), t->val), gcd(t->r));
}
}
// x in l
void split(Node* t, Node*& l, Node*& r, int x) {
if (!t) {
l = r = nullptr;
} else {
if (x < t->x) {
r = t;
split(t->l, l, t->l, x);
} else {
l = t;
split(t->r, t->r, r, x);
}
update(t);
}
}
void merge(Node*& t, Node* l, Node* r) {
if (!l || !r) {
t = l ? l : r;
} else {
if (l->prio > r->prio) {
t = l;
merge(t->r, t->r, r);
} else {
t = r;
merge(t->l, l, t->l);
}
update(t);
}
}
void update_x(Node*& t, int x, ll val) {
Node* t1, *t2, *t3;
split(t, t1, t2, x-1);
split(t2, t2, t3, x);
if (!t2) t2 = init_node(x, val);
else t2->val = t2->gcd = val;
merge(t, t1, t2);
merge(t, t, t3);
}
ll gcdRS(Node* t, int R, int S) {
Node* t1, *t2, *t3;
split(t, t1, t2, R-1);
split(t2, t2, t3, S);
ll res = gcd(t2);
merge(t, t1, t2);
merge(t, t, t3);
return res;
}
// gcd of [P, Q]x[R, S], knowing that t covers [a,b]
ll query(RowNode* t, int P, int Q, int R, int S, int a, int b) {
if (!t || Q < a || P > b || a > b) return -1;
if (P <= a && b <= Q) {
return gcdRS(thick_row(t), R, S);
} else {
ll gcd_x = (P <= t->x && t->x <= Q) ? gcdRS(row(t), R, S) : -1;
return gcd(gcd_x, gcd(query(t->l, P, Q, R, S, a, t->x-1),
query(t->r, P, Q, R, S, t->x+1, b)));
}
}
ll find_gcd(Node* t, int Q) {
if (!t) return -1;
if (t->x == Q) return t->val;
else {
return find_gcd(Q < t->x ? t->l : t->r, Q);
}
}
void pointUpdateThickrow(RowNode*& t, int Q) {
// We don't need to fully recalculate thickrow, because only x=Q had
// changed.
Node* t1, *t2, *t3;
split(t->thick_row, t1, t2, Q-1);
split(t2, t2, t3, Q);
ll newval = gcd( find_gcd(thick_row(t->l), Q),
gcd( find_gcd(thick_row(t->r), Q), find_gcd(t->row, Q)) );
if (!t2) t2 = init_node(Q, newval);
else t2->val = t2->gcd = newval;
merge(t->thick_row, t1, t2);
merge(t->thick_row, t->thick_row, t3);
}
RowNode* find(RowNode* t, int P) {
if (!t) {
return nullptr;
}
else if (P < t->x) {
return find(t->l, P);
}
else if (P > t->x) {
return find(t->r, P);
}
else {
return t;
}
}
void copy(Node* src, Node*& dst) {
if (!src) dst = nullptr;
else {
dst = new Node;
copy(src->l, dst->l);
copy(src->r, dst->r);
dst->x = src->x;
dst->val = src->val;
dst->prio = src->prio;
dst->gcd = src->gcd;
}
}
Node* join(Node* t1, Node* t2) {
Node* t;
if (!t1 && !t2) t = nullptr;
else if (!t1) copy(t2, t);
else if (!t2) copy(t1, t);
else {
if (t1->prio < t2->prio) swap(t1, t2);
t = new Node;
Node* t2l, *t2x, *t2r;
ll t2gcd = gcd(t2);
split(t2, t2l, t2x, t1->x-1);
split(t2x, t2x, t2r, t1->x);
t->x = t1->x;
t->val = gcd(val(t1), val(t2x));
t->gcd = gcd(gcd(t1), t2gcd);
t->prio = t1->prio;
t->l = join(t1->l, t2l);
t->r = join(t1->r, t2r);
merge(t2, t2l, t2x);
merge(t2, t2, t2r);
}
return t;
}
// P in l.
void split(RowNode* t, RowNode*& l, RowNode*& r, int P) {
if (!t) {
l = r = nullptr;
} else {
if (P < t->x) {
r = t;
split(t->l, l, t->l, P);
} else {
l = t;
split(t->r, t->r, r, P);
}
t->thick_row = join(join(thick_row(t->l), t->row), thick_row(t->r));
}
}
void set_rec(RowNode*& t, int P, int Q, ll val, int prio) {
if (!t) {
t = new RowNode;
t->l = t->r = nullptr;
t->x = P;
t->row = init_node(Q, val);
t->prio = prio;
} else {
if (prio > t->prio) {
// prio > 0 means we won't find P.
RowNode* child = t;
t = new RowNode;
t->x = P;
split(child, t->l, t->r, P);
t->row = init_node(Q, val);
// (Q,val) will be updated as part of pointUpdateThickrow
t->thick_row = join(thick_row(t->l), thick_row(t->r));
t->prio = prio;
} else {
if (P < t->x) set_rec(t->l, P, Q, val, prio);
else if (P == t->x) update_x(t->row, Q, val);
else set_rec(t->r, P, Q, val, prio);
}
}
pointUpdateThickrow(t, Q);
}
void set(RowNode*& t, int P, int Q, ll val) {
set_rec(t, P, Q, val, find(t, P) ? 0 : rand());
}
struct SSTNode {
SSTNode *l = nullptr, *r = nullptr;
Node* row = nullptr;
};
Node* row(SSTNode* t) {
return t ? t->row : nullptr;
}
// t is [a, b), x \in [a,b)
void set(SSTNode*& t, int P, int Q, ll val, int a, int b) {
if (!t) t = new SSTNode;
if (b > a+1) {
int m = (a+b)/2;
if (P < m) set(t->l, P, Q, val, a, m);
else set(t->r, P, Q, val, m, b);
// Update row, using that most gcd are not expected to change.
Node* t1, *t2, *t3;
split(t->row, t1, t2, Q-1);
split(t2, t2, t3, Q);
ll new_gcd = gcd(val, gcd(find_gcd(row(t->l), Q), find_gcd(row(t->r), Q)));
if (!t2) {
t2 = init_node(Q, new_gcd);
} else {
t2->val = t2->gcd = new_gcd;
}
merge(t->row, t1, t2);
merge(t->row, t->row, t3);
} else {
update_x(t->row, Q, val);
}
}
// gcd of [P, Q]x[R, S], knowing that t covers [a,b)
ll query(SSTNode* t, int P, int Q, int R, int S, int a, int b) {
if (!t || Q < a || P >= b || a >= b) return -1;
if (P <= a && b-1 <= Q) {
// cout << "*query t=[" << a << "," << b << ") P=" << P << " Q=" << Q << endl;
ll res = gcdRS(t->row, R, S);
// cout << " res = " << res << endl;
return res;
} else {
ll m = (a+b)/2;
ll res = gcd(query(t->l, P, Q, R, S, a, m),
query(t->r, P, Q, R, S, m, b));
// cout << "query t=[" << a << "," << b << ") P=" << P << " Q=" << Q << endl;
// cout << " res = " << res << endl;
return res;
}
}
void print(Node* t) {
if (t) {
cout << "[";
print(t->l);
cout << " " << t->x << "|" << t->val << "|" << t->gcd << "-" << t->prio << " ";
print(t->r);
cout << "]";
}
}
void print(SSTNode* t, int a, int b) {
if (t) {
cout << "a=" << a << " b=" << b << " ";
print(row(t));
cout << endl;
if (a+1 < b) {
int m = (a+b)/2;
print(t->l, a, m);
print(t->r, m, b);
}
}
}
RowNode* globalt = nullptr;
SSTNode* gn = nullptr;
int globalRows = -1;
int Rp2 = 1;
void init(int R, int C) {
globalRows = R;
while (Rp2 <= R) Rp2*=2;
}
void update(int P, int Q, ll K) {
//set(globalt, P, Q, K);
set(gn, P, Q, K, 0, Rp2);
// print(gn, 0, Rp2);
// cout << endl;
}
ll calculate(int P, int Q, int R, int S) {
// ll res = #include <iostream>
#include <vector>
#include <string>
//#include "game.h"
using namespace std;
bool safecheck = false;
typedef long long ll;
struct Node {
Node *l, *r;
int x;
ll val;
int prio;
ll gcd;
};
struct RowNode {
RowNode *l, *r;
int x;
Node* row;
Node* thick_row;
int prio;
};
Node* row(RowNode* t) {
return t ? t->row : nullptr;
}
Node* thick_row(RowNode* t) {
return t ? t->thick_row : nullptr;
}
ll gcd(Node* t) {
return t ? t->gcd : -1;
}
ll val(Node* t) {
return t ? t->val : -1;
}
ll gcdrec(ll a, ll b) {
return a == 0 ? b : gcdrec(b%a, a);
}
ll gcd(ll a, ll b) {
if (a == -1 || b == -1) return a == -1 ? b : a;
return gcdrec(a, b);
}
Node* init_node(int x, ll val) {
Node* t = new Node;
t->l = t->r = nullptr;
t->x = x;
t->val = t->gcd = val;
t->prio = rand();
return t;
}
void update(Node* t) {
if (t) {
t->gcd = gcd(gcd(gcd(t->l), t->val), gcd(t->r));
}
}
// x in l
void split(Node* t, Node*& l, Node*& r, int x) {
if (!t) {
l = r = nullptr;
} else {
if (x < t->x) {
r = t;
split(t->l, l, t->l, x);
} else {
l = t;
split(t->r, t->r, r, x);
}
update(t);
}
}
void merge(Node*& t, Node* l, Node* r) {
if (!l || !r) {
t = l ? l : r;
} else {
if (l->prio > r->prio) {
t = l;
merge(t->r, t->r, r);
} else {
t = r;
merge(t->l, l, t->l);
}
update(t);
}
}
void update_x(Node*& t, int x, ll val) {
Node* t1, *t2, *t3;
split(t, t1, t2, x-1);
split(t2, t2, t3, x);
if (!t2) t2 = init_node(x, val);
else t2->val = t2->gcd = val;
merge(t, t1, t2);
merge(t, t, t3);
}
ll gcdRS(Node* t, int R, int S) {
Node* t1, *t2, *t3;
split(t, t1, t2, R-1);
split(t2, t2, t3, S);
ll res = gcd(t2);
merge(t, t1, t2);
merge(t, t, t3);
return res;
}
// gcd of [P, Q]x[R, S], knowing that t covers [a,b]
ll query(RowNode* t, int P, int Q, int R, int S, int a, int b) {
if (!t || Q < a || P > b || a > b) return -1;
if (P <= a && b <= Q) {
return gcdRS(thick_row(t), R, S);
} else {
ll gcd_x = (P <= t->x && t->x <= Q) ? gcdRS(row(t), R, S) : -1;
return gcd(gcd_x, gcd(query(t->l, P, Q, R, S, a, t->x-1),
query(t->r, P, Q, R, S, t->x+1, b)));
}
}
ll find_gcd(Node* t, int Q) {
if (!t) return -1;
if (t->x == Q) return t->val;
else {
return find_gcd(Q < t->x ? t->l : t->r, Q);
}
}
void pointUpdateThickrow(RowNode*& t, int Q) {
// We don't need to fully recalculate thickrow, because only x=Q had
// changed.
Node* t1, *t2, *t3;
split(t->thick_row, t1, t2, Q-1);
split(t2, t2, t3, Q);
ll newval = gcd( find_gcd(thick_row(t->l), Q),
gcd( find_gcd(thick_row(t->r), Q), find_gcd(t->row, Q)) );
if (!t2) t2 = init_node(Q, newval);
else t2->val = t2->gcd = newval;
merge(t->thick_row, t1, t2);
merge(t->thick_row, t->thick_row, t3);
}
RowNode* find(RowNode* t, int P) {
if (!t) {
return nullptr;
}
else if (P < t->x) {
return find(t->l, P);
}
else if (P > t->x) {
return find(t->r, P);
}
else {
return t;
}
}
void copy(Node* src, Node*& dst) {
if (!src) dst = nullptr;
else {
dst = new Node;
copy(src->l, dst->l);
copy(src->r, dst->r);
dst->x = src->x;
dst->val = src->val;
dst->prio = src->prio;
dst->gcd = src->gcd;
}
}
Node* join(Node* t1, Node* t2) {
Node* t;
if (!t1 && !t2) t = nullptr;
else if (!t1) copy(t2, t);
else if (!t2) copy(t1, t);
else {
if (t1->prio < t2->prio) swap(t1, t2);
t = new Node;
Node* t2l, *t2x, *t2r;
ll t2gcd = gcd(t2);
split(t2, t2l, t2x, t1->x-1);
split(t2x, t2x, t2r, t1->x);
t->x = t1->x;
t->val = gcd(val(t1), val(t2x));
t->gcd = gcd(gcd(t1), t2gcd);
t->prio = t1->prio;
t->l = join(t1->l, t2l);
t->r = join(t1->r, t2r);
merge(t2, t2l, t2x);
merge(t2, t2, t2r);
}
return t;
}
// P in l.
void split(RowNode* t, RowNode*& l, RowNode*& r, int P) {
if (!t) {
l = r = nullptr;
} else {
if (P < t->x) {
r = t;
split(t->l, l, t->l, P);
} else {
l = t;
split(t->r, t->r, r, P);
}
t->thick_row = join(join(thick_row(t->l), t->row), thick_row(t->r));
}
}
void set_rec(RowNode*& t, int P, int Q, ll val, int prio) {
if (!t) {
t = new RowNode;
t->l = t->r = nullptr;
t->x = P;
t->row = init_node(Q, val);
t->prio = prio;
} else {
if (prio > t->prio) {
// prio > 0 means we won't find P.
RowNode* child = t;
t = new RowNode;
t->x = P;
split(child, t->l, t->r, P);
t->row = init_node(Q, val);
// (Q,val) will be updated as part of pointUpdateThickrow
t->thick_row = join(thick_row(t->l), thick_row(t->r));
t->prio = prio;
} else {
if (P < t->x) set_rec(t->l, P, Q, val, prio);
else if (P == t->x) update_x(t->row, Q, val);
else set_rec(t->r, P, Q, val, prio);
}
}
pointUpdateThickrow(t, Q);
}
void set(RowNode*& t, int P, int Q, ll val) {
set_rec(t, P, Q, val, find(t, P) ? 0 : rand());
}
struct SSTNode {
SSTNode *l = nullptr, *r = nullptr;
Node* row = nullptr;
};
Node* row(SSTNode* t) {
return t ? t->row : nullptr;
}
// t is [a, b), x \in [a,b)
void set(SSTNode*& t, int P, int Q, ll val, int a, int b) {
if (!t) t = new SSTNode;
if (b > a+1) {
int m = (a+b)/2;
if (P < m) set(t->l, P, Q, val, a, m);
else set(t->r, P, Q, val, m, b);
// Update row, using that most gcd are not expected to change.
Node* t1, *t2, *t3;
split(t->row, t1, t2, Q-1);
split(t2, t2, t3, Q);
ll new_gcd = gcd(val, gcd(find_gcd(row(t->l), Q), find_gcd(row(t->r), Q)));
if (!t2) {
t2 = init_node(Q, new_gcd);
} else {
t2->val = t2->gcd = new_gcd;
}
merge(t->row, t1, t2);
merge(t->row, t->row, t3);
} else {
update_x(t->row, Q, val);
}
}
// gcd of [P, Q]x[R, S], knowing that t covers [a,b)
ll query(SSTNode* t, int P, int Q, int R, int S, int a, int b) {
if (!t || Q < a || P >= b || a >= b) return -1;
if (P <= a && b-1 <= Q) {
// cout << "*query t=[" << a << "," << b << ") P=" << P << " Q=" << Q << endl;
ll res = gcdRS(t->row, R, S);
// cout << " res = " << res << endl;
return res;
} else {
ll m = (a+b)/2;
ll res = gcd(query(t->l, P, Q, R, S, a, m),
query(t->r, P, Q, R, S, m, b));
// cout << "query t=[" << a << "," << b << ") P=" << P << " Q=" << Q << endl;
// cout << " res = " << res << endl;
return res;
}
}
void print(Node* t) {
if (t) {
cout << "[";
print(t->l);
cout << " " << t->x << "|" << t->val << "|" << t->gcd << "-" << t->prio << " ";
print(t->r);
cout << "]";
}
}
void print(SSTNode* t, int a, int b) {
if (t) {
cout << "a=" << a << " b=" << b << " ";
print(row(t));
cout << endl;
if (a+1 < b) {
int m = (a+b)/2;
print(t->l, a, m);
print(t->r, m, b);
}
}
}
RowNode* globalt = nullptr;
SSTNode* gn = nullptr;
int globalRows = -1;
int Rp2 = 1;
void init(int R, int C) {
globalRows = R;
while (Rp2 <= R) Rp2*=2;
}
void update(int P, int Q, ll K) {
//set(globalt, P, Q, K);
set(gn, P, Q, K, 0, Rp2);
// print(gn, 0, Rp2);
// cout << endl;
}
ll calculate(int P, int Q, int R, int S) {
// ll res = query(globalt, P, R, Q, S, 0, globalRows-1);
ll res = query(gn, P, R, Q, S, 0, Rp2);
return res == -1 ? 0 : res;
}
Compilation message
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:366:23: error: a function-definition is not allowed here before '{' token
366 | Node* row(RowNode* t) {
| ^
game.cpp:370:29: error: a function-definition is not allowed here before '{' token
370 | Node* thick_row(RowNode* t) {
| ^
game.cpp:374:17: error: a function-definition is not allowed here before '{' token
374 | ll gcd(Node* t) {
| ^
game.cpp:377:17: error: a function-definition is not allowed here before '{' token
377 | ll val(Node* t) {
| ^
game.cpp:381:23: error: a function-definition is not allowed here before '{' token
381 | ll gcdrec(ll a, ll b) {
| ^
game.cpp:385:20: error: a function-definition is not allowed here before '{' token
385 | ll gcd(ll a, ll b) {
| ^
game.cpp:390:32: error: a function-definition is not allowed here before '{' token
390 | Node* init_node(int x, ll val) {
| ^
game.cpp:399:22: error: a function-definition is not allowed here before '{' token
399 | void update(Node* t) {
| ^
game.cpp:406:48: error: a function-definition is not allowed here before '{' token
406 | void split(Node* t, Node*& l, Node*& r, int x) {
| ^
game.cpp:421:40: error: a function-definition is not allowed here before '{' token
421 | void merge(Node*& t, Node* l, Node* r) {
| ^
game.cpp:436:40: error: a function-definition is not allowed here before '{' token
436 | void update_x(Node*& t, int x, ll val) {
| ^
game.cpp:446:33: error: a function-definition is not allowed here before '{' token
446 | ll gcdRS(Node* t, int R, int S) {
| ^
game.cpp:457:64: error: a function-definition is not allowed here before '{' token
457 | ll query(RowNode* t, int P, int Q, int R, int S, int a, int b) {
| ^
game.cpp:468:29: error: a function-definition is not allowed here before '{' token
468 | ll find_gcd(Node* t, int Q) {
| ^
game.cpp:476:46: error: a function-definition is not allowed here before '{' token
476 | void pointUpdateThickrow(RowNode*& t, int Q) {
| ^
game.cpp:491:34: error: a function-definition is not allowed here before '{' token
491 | RowNode* find(RowNode* t, int P) {
| ^
game.cpp:506:34: error: a function-definition is not allowed here before '{' token
506 | void copy(Node* src, Node*& dst) {
| ^
game.cpp:519:32: error: a function-definition is not allowed here before '{' token
519 | Node* join(Node* t1, Node* t2) {
| ^
game.cpp:544:57: error: a function-definition is not allowed here before '{' token
544 | void split(RowNode* t, RowNode*& l, RowNode*& r, int P) {
| ^
game.cpp:559:59: error: a function-definition is not allowed here before '{' token
559 | void set_rec(RowNode*& t, int P, int Q, ll val, int prio) {
| ^
game.cpp:586:45: error: a function-definition is not allowed here before '{' token
586 | void set(RowNode*& t, int P, int Q, ll val) {
| ^
game.cpp:595:23: error: a function-definition is not allowed here before '{' token
595 | Node* row(SSTNode* t) {
| ^
game.cpp:600:59: error: a function-definition is not allowed here before '{' token
600 | void set(SSTNode*& t, int P, int Q, ll val, int a, int b) {
| ^
game.cpp:624:64: error: a function-definition is not allowed here before '{' token
624 | ll query(SSTNode* t, int P, int Q, int R, int S, int a, int b) {
| ^
game.cpp:641:21: error: a function-definition is not allowed here before '{' token
641 | void print(Node* t) {
| ^
game.cpp:651:38: error: a function-definition is not allowed here before '{' token
651 | void print(SSTNode* t, int a, int b) {
| ^
game.cpp:669:25: error: a function-definition is not allowed here before '{' token
669 | void init(int R, int C) {
| ^
game.cpp:673:33: error: a function-definition is not allowed here before '{' token
673 | void update(int P, int Q, ll K) {
| ^
game.cpp:679:42: error: a function-definition is not allowed here before '{' token
679 | ll calculate(int P, int Q, int R, int S) {
| ^
game.cpp:347:6: warning: unused variable 'safecheck' [-Wunused-variable]
347 | bool safecheck = false;
| ^~~~~~~~~
game.cpp:664:10: warning: unused variable 'globalt' [-Wunused-variable]
664 | RowNode* globalt = nullptr;
| ^~~~~~~
game.cpp:665:10: warning: unused variable 'gn' [-Wunused-variable]
665 | SSTNode* gn = nullptr;
| ^~
game.cpp:666:5: warning: unused variable 'globalRows' [-Wunused-variable]
666 | int globalRows = -1;
| ^~~~~~~~~~
game.cpp:667:5: warning: unused variable 'Rp2' [-Wunused-variable]
667 | int Rp2 = 1;
| ^~~
game.cpp:683:1: error: expected '}' at end of input
683 | }
| ^
game.cpp:339:42: note: to match this '{'
339 | ll calculate(int P, int Q, int R, int S) {
| ^
game.cpp:683:1: warning: no return statement in function returning non-void [-Wreturn-type]
683 | }
| ^