#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int r, c;
struct Node1
{
Node1() : val(0), lc(NULL), rc(NULL) {}
ll val; Node1 *lc, *rc;
};
struct Node2
{
Node2() : val(NULL), lc(NULL), rc(NULL) {}
Node1 *val; Node2 *lc, *rc;
};
Node2 *root;
void init(int R, int C)
{
r=R; c=C;
root=new Node2();
}
void update1(Node1* node, int tl, int tr, int x, ll val)
{
if(tl==tr) { node->val=val; return; }
int mid=tl+tr>>1;
if(x<=mid)
{
if(node->lc==NULL) node->lc=new Node1();
update1(node->lc, tl, mid, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node1();
update1(node->rc, mid+1, tr, x, val);
}
node->val=0;
if(node->lc!=NULL) node->val=__gcd(node->val, node->lc->val);
if(node->rc!=NULL) node->val=__gcd(node->val, node->rc->val);
}
ll query1(Node1* node, int tl, int tr, int lx, int rx)
{
if(tr<lx || rx<tl) return 0;
if(lx<=tl && tr<=rx) return node->val;
int mid=tl+tr>>1;
ll ret=0;
if(node->lc!=NULL) ret=__gcd(ret, query1(node->lc, tl, mid, lx, rx));
if(node->rc!=NULL) ret=__gcd(ret, query1(node->rc, mid+1, tr, lx, rx));
return ret;
}
void update2(Node2* node, int tl, int tr, int y, int x, ll val)
{
if(node->val==NULL) node->val=new Node1();
if(tl==tr) { update1(node->val, 1, c, x, val); return; }
int mid=tl+tr>>1;
if(y<=mid)
{
if(node->lc==NULL) node->lc=new Node2();
update2(node->lc, tl, mid, y, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node2();
update2(node->rc, mid+1, tr, y, x, val);
}
ll t=0;
if(node->lc!=NULL) t=__gcd(t, query1(node->lc->val, 1, c, x, x));
if(node->rc!=NULL) t=__gcd(t, query1(node->rc->val, 1, c, x, x));
update1(node->val, 1, c, x, t);
}
ll query2(Node2 *node, int tl, int tr, int ly, int ry, int lx, int rx)
{
if(tr<ly || ry<tl) return 0;
if(ly<=tl && tr<=ry) return query1(node->val, 1, c, lx, rx);
int mid=tl+tr>>1;
ll ret=0;
if(node->lc!=NULL) ret=__gcd(ret, query2(node->lc, tl, mid, ly, ry, lx, rx));
if(node->rc!=NULL) ret=__gcd(ret, query2(node->rc, mid+1, tr, ly, ry, lx, rx));
return ret;
}
void update(int P, int Q, ll K)
{
P++; Q++;
update2(root, 1, r, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
P++; Q++; U++; V++;
return query2(root, 1, r, 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;
^~~
game.cpp: In function 'void update1(Node1*, int, int, int, ll)':
game.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'll query1(Node1*, int, int, int, int)':
game.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'void update2(Node2*, int, int, int, int, ll)':
game.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'll query2(Node2*, int, int, int, int, int, int)':
game.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
4 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
384 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
