#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "game.h"
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
int R, C;
int gcd(int x, int y) {
if (x == 0 || y == 0) return max(x, y);
return __gcd(x, y);
}
struct nodeY
{
int lo, hi;
nodeY *l=0, *r=0;
ll val = 0;
};
struct nodeX {
nodeX *l=0, *r=0;
nodeY *root=0;
nodeX() {
l = 0, r = 0;
root = new nodeY();
root->lo = 0, root->hi = C - 1;
}
};
nodeX *root=0;
ll qry2(nodeY *cur, int yL, int yH) {
if (!cur) return 0;
if (yH < cur->lo || cur->hi < yL) return 0;
if (yL <= cur->lo && cur->hi <= yH) return cur->val;
return gcd(qry2(cur->l, yL, yH), qry2(cur->r, yL, yH));
}
ll qry1(nodeX *cur, int l, int r, int xL, int xH, int yL, int yH) {
if (!cur) return 0;
if (r < xL || xH < l) return 0;
if (xL <= l && r <= xH) return qry2(cur->root, yL, yH);
int m = (l + r) / 2;
return gcd(qry1(cur->l, l, m, xL, xH, yL, yH), qry1(cur->r, m+1, r, xL, xH, yL, yH));
}
void upd2(nodeY *cur, int y, ll val) {
if (cur->lo == cur->hi) {
cur->val = val;
return;
}
int m = (cur->lo + cur->hi) / 2;
nodeY *&nxt = (y <= m) ? cur->l : cur->r;
if (!nxt) {
nxt = new nodeY();
nxt->lo = y, nxt->hi = y;
nxt->val = val;
} else if (nxt->lo <= y && y <= nxt->hi)
upd2(nxt, y, val);
else {
nodeY *nx = new nodeY();
nx->lo = cur->lo, nx->hi = cur->hi;
do {
if (y <= m)
nx->hi = m;
else
nx->lo = m + 1;
m = (nx->lo + nx->hi) / 2;
} while ((y <= m) == (nxt->lo <= m));
if (y <= m)
nx->r = nxt;
else
nx->l = nxt;
nxt = nx;
upd2(nx, y, val);
}
ll a = 0, b = 0;
if (cur->l) a = cur->l->val;
if (cur->r) b = cur->r->val;
cur->val = gcd(a, b);
}
void upd1(int l, int r, nodeX *cur, int x, int y, ll val) {
if (l == r) {
upd2(cur->root, y, val);
return;
}
int m = (l + r) / 2;
ll a = 0, b = 0;
if (x <= m) {
if (!cur->l) cur->l = new nodeX();
upd1(l, m, cur->l, x, y, val);
} else {
if (!cur->r) cur->r = new nodeX();
upd1(m+1, r, cur->r, x, y, val);
}
if (cur->l) a = qry2(cur->l->root, y, y);
if (cur->r) b = qry2(cur->r->root, y, y);
upd2(cur->root, y, gcd(a, b));
}
void init(int R1, int C1) {
R = R1, C = C1;
root = new nodeX();
}
void update(int p, int q, ll k) {
upd1(0, R-1, root, p, q, k);
}
ll calculate(int p, int q, int u, int v) {
return qry1(root, 0, R-1, p, u, q, v);
}
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;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
