| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 962574 |
2024-04-13T20:28:14 Z |
Leo121 |
Game (IOI13_game) |
C++14 |
|
1 ms |
348 KB |
#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) bg(v), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define lb lower_bound
#define ub upper_bound
#define SZ(v) int(v.size())
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
using namespace std;
///#include <bits/extc++.h>
///using namespace __gnu_pbds;
///typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long double ld;
typedef double db;
typedef long long lli;
///typedef __int128 Int;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const int inf = 1e4;
const int MX = 3e5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
auto randis = uniform_int_distribution<int>(numeric_limits<int>::min(), numeric_limits<int>::max());
struct Node {
// the value and priority of the node respectively
int pri, x, y;
ll val, gcd;
// pointer to left and right child (NULL means no child)
Node *left, *right;
Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
};
/**
* pass in root as pointer, left and right as references
* to a node pointer so we can modify them
* (alternatively, we can return left and right pointers
* as an std::pair)
*/
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;
}
inline ll gcd(Node * t){return t ? t->gcd : 0;}
void split(Node *root, int x, int y, Node *&left, Node *&right) {
if (!root) {
left = right = NULL;
return;
}
if (root->y < y || (root->y == y && root->x <= x)) {
split(root->right, x, y, root->right, right);
left = root;
} else {
split(root->left, x, y, left, root->left);
right = root;
}
root->gcd = gcd2(gcd2(gcd(root), gcd(root->left)), gcd(root->right));
}
/**
* merge left and right pointers into root which
* is a reference to a pointer to enable
* modification within the function
*/
void merge(Node *&r, Node *left, Node *right) {
if (!left || !right) {
r = left ? left : right;
return;
}
if (left->pri < right->pri) {
merge(left->right, left->right, right);
r = left;
} else {
merge(right->left, left, right->left);
r = right;
}
r->gcd = gcd2(gcd2(gcd(r), gcd(r->left)), gcd(r->right));
}
struct nodest{
int l, r;
Node * root;
};
nodest st[660000];
int idx = 0;
void pushst(int n, int x, int y, ll val){
if(!st[n].root){
st[n].root = new Node(x, y, val);
return;
}
Node *a, *b, *c, *d;
split(st[n].root, x, y, c, d);
split(c, x - 1, y, a, b);
if(!b)
b = new Node(x, y, val);
else
b->gcd = b->val = val;
merge(st[n].root, a, b);
merge(st[n].root, st[n].root, d);
}
void updatest(int n, int l, int r, int x, int y, ll val){
pushst(n, x, y, val);
if(l == r)
return;
int m = (l + r) / 2;
if(x <= m){
if(st[n].l == -1){
st[n].l = ++ idx;
st[idx].l = st[idx].r = -1;
st[idx].root = NULL;
}
updatest(st[n].l, l, m, x, y, val);
return;
}
if(st[n].r == -1){
st[n].r = ++ idx;
st[idx].l = st[idx].r = -1;
st[idx].root = NULL;
}
updatest(st[n].r, m + 1, r, x, y, val);
}
ll querytr(int n, int yi, int yf){
if(!st[n].root) return 0;
ll ans = 0;
Node *a, *b, *c, *d;
split(st[n].root, -1, yf + 1, c, d);
split(c, -1, yi, a, b);
ans = (!b) ? 0 : b->gcd;
merge(st[n].root, a, b);
merge(st[n].root, st[n].root, d);
return ans;
}
ll query(int n, int l, int r, int xi, int xf, int yi, int yf){
if(n == -1) return 0;
if(l > xf || r < xi) return 0;
if(xi <= l && r <= xf) return querytr(n, yi, yf);
int m = (l + r) / 2;
return gcd2(query(st[n].l, l, m, xi, xf, yi, yf), query(st[n].r, m + 1, r, xi, xf, yi, yf));
}
int Ri;
void init(int R, int C) {
st[0].root = NULL;
st[0].l = -1;
st[0].r = -1;
Ri = R;
}
void update(int P, int Q, long long K) {
updatest(0, 0, Ri - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
/* ... */
return query(0, 0, Ri - 1, P, U, Q, V);
}
Compilation message
game.cpp: In constructor 'Node::Node(int, int, ll)':
game.cpp:59:10: warning: 'Node::gcd' will be initialized after [-Wreorder]
59 | ll val, gcd;
| ^~~
game.cpp:58:11: warning: 'int Node::x' [-Wreorder]
58 | int pri, x, y;
| ^
game.cpp:62:2: warning: when initialized here [-Wreorder]
62 | Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
| ^~~~
game.cpp:58:14: warning: 'Node::y' will be initialized after [-Wreorder]
58 | int pri, x, y;
| ^
game.cpp:58:6: warning: 'int Node::pri' [-Wreorder]
58 | int pri, x, y;
| ^~~
game.cpp:62:2: warning: when initialized here [-Wreorder]
62 | Node(int x, int y, ll v) : val(v), gcd(v), x(x), y(y), pri(randis(rng)), left(NULL), right(NULL){};
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 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 |
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 |
1 ms |
348 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 |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
