#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long gcd2(long long X, long long Y) {
long long tmp;
if(X==0&&Y==0) return 0;
if(X==0) return Y;
if(Y==0) return X;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
struct colNode {
int l, r;
ll st;
colNode *left, *right;
colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
};
set<pair<int, int>> isNew;
ll query(int x, int y, colNode *cur) {
if(cur == NULL) {
// cerr << " inv " << endl;
return 0;
}
// cerr << " " << cur->l << " " << cur->r << ": " << cur->st << endl;
if(x >= cur->r || y <= cur->l) {
// cerr << " i" << cur->l << " " << cur->r << ": " << cur->st << endl;
return 0;
}
if(y >= cur->r && x <= cur->l) {
// cerr << " " << cur->l << " " << cur->r << ": " << cur->st << endl;
return cur->st;
}
if(cur->left==NULL && cur->right==NULL)
if(cur->right==NULL) return query(x, y, cur->left);
if(cur->left==NULL) return query(x, y, cur->right);
return gcd2(query(x, y, cur->left),
query(x, y, cur->right));
}
void update(int j, ll val, colNode *cur, colNode *rowL, colNode *rowR) {
if(cur == NULL) return;
if(j < cur->l || j >= cur->r) return;
if(cur->l + 1 == cur->r) {
if(rowL == NULL && rowR == NULL) cur->st = val;
else if(rowL == NULL) cur->st = query(j, j+1, rowR);
else if(rowR == NULL) cur->st = query(j, j+1, rowL);
else cur->st = gcd2(query(j, j+1, rowL), query(j, j+1, rowR));
return;
}
int mid = (cur->l + cur->r)/2;
if(j < mid) {
if(cur->left == NULL) {
cur->left = new colNode(j, j+1);
} else if(cur->left->l != cur->l || cur->left->r != mid) {
int mid2 = (cur->l+mid)/2;
if(cur->left->l < mid2) {
cur->left->left = new colNode(cur->left->l, cur->left->r);
cur->left->left->st = cur->left->st;
} else {
cur->left->right = new colNode(cur->left->l, cur->left->r);
cur->left->right->st = cur->left->st;
}
cur->left->l = cur->l;
cur->left->r = mid;
}
update(j, val, cur->left, rowL, rowR);
} else {
if(cur->right == NULL) {
cur->right = new colNode(j, j+1);
} else if(cur->right->l != mid || cur->right->r != cur->r) {
int mid2 = (cur->r+mid)/2;
if(cur->right->l < mid2) {
cur->right->left = new colNode(cur->right->l, cur->right->r);
cur->right->left->st = cur->right->st;
} else {
cur->right->right = new colNode(cur->right->l, cur->right->r);
cur->right->right->st = cur->right->st;
}
cur->right->l = mid;
cur->right->r = cur->r;
}
update(j, val, cur->right, rowL, rowR);
}
if(cur->left==NULL) cur->st = cur->right->st;
else if(cur->right==NULL) cur->st = cur->left->st;
else cur->st = gcd2(cur->left->st, cur->right->st);
}
void copy(colNode *orig, colNode *next) {
if(orig == NULL) return;
next->l = orig->l; next->r = orig->r;
next->st = orig->st;
if(orig->left != NULL) { next->left = new colNode(0, 0); copy(orig->left, next->left); }
if(orig->right != NULL) { next->right = new colNode(0, 0); copy(orig->right, next->right); }
}
struct rowNode {
int l, r;
rowNode *left, *right;
colNode *col;
rowNode(int lv, int rv): left(NULL), right(NULL) {l=lv; r=rv; col = new colNode(0, C);};
};
void update(int i, int j, ll val, rowNode *cur) {
if(cur == NULL) return;
if(i < cur->l || i >= cur->r) return;
int mid = (cur->l + cur->r)/2;
if(cur->l+1 == cur-> r) {
} else if(i < mid) {
if(cur->left == NULL) {
cur->left = new rowNode(i, i+1);
} else if(cur->left->l != cur->l || cur->left->r != mid) {
int mid2 = (cur->l+mid)/2;
if(cur->left->l < mid2) {
cur->left->left = new rowNode(cur->left->l, cur->left->r);
copy(cur->left->col, cur->left->left->col);
} else {
cur->left->right = new rowNode(cur->left->l, cur->left->r);
copy(cur->left->col, cur->left->right->col);
}
cur->left->l = cur->l;
cur->left->r = mid;
}
update(i, j, val, cur->left);
} else {
if(cur->right == NULL)
cur->right = new rowNode(mid, cur->r);
update(i, j, val, cur->right);
}
if(cur->left == NULL && cur->right == NULL) update(j, val, cur->col, NULL, NULL);
else if(cur->left == NULL) update(j, val, cur->col, NULL, cur->right->col);
else if(cur->right == NULL) update(j, val, cur->col, cur->left->col, NULL);
else update(j, val, cur->col, cur->left->col, cur->right->col);
}
ll query(int x, int y, int nx, int ny, rowNode *cur) {
if(cur == NULL) return 0;
if(x >= cur->r || y <= cur->l) return 0;
if(y >= cur->r && x <= cur->l) return query(nx, ny, cur->col);
if(cur->right==NULL) return query(x, y, nx, ny, cur->left);
if(cur->left==NULL) return query(x, y, nx, ny, cur->right);
return gcd2(query(x, y, nx, ny, cur->left),
query(x, y, nx, ny, cur->right));
}
rowNode root(0,1);
void init(signed r, signed c) {
R = r;
C = c;
root = *(new rowNode(0, R));
}
void update(signed P, signed Q, long long K) {
update(P, Q, K, &root);
}
long long calculate(signed P, signed Q, signed U, signed V) {
return query(P, U+1, Q, V+1, &root);;
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
game.cpp: In constructor 'colNode::colNode(int, int)':
game.cpp:24:21: warning: 'colNode::right' will be initialized after [-Wreorder]
colNode *left, *right;
^~~~~
game.cpp:23:8: warning: 'long long int colNode::st' [-Wreorder]
ll st;
^~
game.cpp:25:5: warning: when initialized here [-Wreorder]
colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
488 KB |
Output is correct |
| 2 |
Correct |
2 ms |
492 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
544 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
544 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
544 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
544 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
616 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
616 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
