#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int R, C;
struct Node1
{
ll val; int lc, rc, pos;
Node1() : val(0), lc(-1), rc(-1), pos(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
nodes1.push_back(Node1());
return (int)nodes1.size()-1;
}
struct Node2
{
int val; int lc, rc;
Node2() : val(-1), lc(-1), rc(-1) {}
};
vector<Node2> nodes2;
int newNode2()
{
nodes2.push_back(Node2());
return (int)nodes2.size()-1;
}
void update1(int node, int tl, int tr, int x, ll val)
{
//printf("%d %d %d %d %lld\n", node, tl, tr, x, val);
if(tl==tr)
{
nodes1[node].val=val;
return;
}
int mid=tl+tr>>1;
if(nodes1[node].pos!=-1)
{
if(nodes1[node].pos<=mid)
{
int t=newNode1(); nodes1[node].lc=t;
nodes1[nodes1[node].lc].pos=nodes1[node].pos;
nodes1[nodes1[node].lc].val=nodes1[node].val;
}
else
{
int t=newNode1(); nodes1[node].rc=t;
nodes1[nodes1[node].rc].pos=nodes1[node].pos;
nodes1[nodes1[node].rc].val=nodes1[node].val;
}
nodes1[node].pos=-1;
}
if(x<=mid)
{
if(nodes1[node].lc==-1)
{
int t=newNode1(); nodes1[node].lc=t;
nodes1[nodes1[node].lc].pos=x;
nodes1[nodes1[node].lc].val=val;
}
else update1(nodes1[node].lc, tl, mid, x, val);
}
else
{
if(nodes1[node].rc==-1)
{
int t=newNode1(); nodes1[node].rc=t;
nodes1[nodes1[node].rc].pos=x;
nodes1[nodes1[node].rc].val=val;
}
update1(nodes1[node].rc, mid+1, tr, x, val);
}
ll t=0;
if(nodes1[node].lc!=-1) t=__gcd(t, nodes1[nodes1[node].lc].val);
if(nodes1[node].rc!=-1) t=__gcd(t, nodes1[nodes1[node].rc].val);
nodes1[node].val=t;
}
ll query1(int node, int tl, int tr, int xl, int xr)
{
//printf("%d %d %d %d %d\n", node, tl, tr, xl, xr);
if(xr<tl || tr<xl) return 0;
if(nodes1[node].pos!=-1)
{
if(tl<=nodes1[node].pos && nodes1[node].pos<=tr) return nodes1[node].val;
else return 0;
}
if(xl<=tl && tr<=xr) return nodes1[node].val;
int mid=tl+tr>>1;
ll ret=0;
if(nodes1[node].lc!=-1) ret=__gcd(ret, query1(nodes1[node].lc, tl, mid, xl, xr));
if(nodes1[node].rc!=-1) ret=__gcd(ret, query1(nodes1[node].rc, mid+1, tr, xl, xr));
return ret;
}
void update2(int node, int tl, int tr, int y, int x, ll val)
{
//printf("%d %d %d %d %d %lld\n", node, tl, tr, y, x, val);
if(nodes2[node].val==-1) { int t=newNode1(); nodes2[node].val=t; }
if(tl==tr)
{
update1(nodes2[node].val, 1, C, x, val);
return;
}
int mid=tl+tr>>1;
if(y<=mid)
{
if(nodes2[node].lc==-1) { int t=newNode2(); nodes2[node].lc=t; }
update2(nodes2[node].lc, tl, mid, y, x, val);
}
else
{
if(nodes2[node].rc==-1) { int t=newNode2(); nodes2[node].rc=t; }
update2(nodes2[node].rc, mid+1, tr, y, x, val);
}
ll t=0;
if(nodes2[node].lc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].lc].val, 1, C, x, x));
if(nodes2[node].rc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].rc].val, 1, C, x, x));
update1(nodes2[node].val, 1, C, x, t);
}
ll query2(int node, int tl, int tr, int yl, int yr, int xl, int xr)
{
//printf("%d %d %d %d %d %d %d\n", node, tl, tr, yl, yr, xl, xr);
if(yr<tl || tr<yl) return 0;
if(yl<=tl && tr<=yr)
{
if(nodes2[node].val!=-1) return query1(nodes2[node].val, 1, C, xl, xr);
else return 0;
}
int mid=tl+tr>>1;
ll ret=0;
if(nodes2[node].lc!=-1) ret=__gcd(ret, query2(nodes2[node].lc, tl, mid, yl, yr, xl, xr));
if(nodes2[node].rc!=-1) ret=__gcd(ret, query2(nodes2[node].rc, mid+1, tr, yl, yr, xl, xr));
return ret;
}
int root;
void init(int _R, int _C)
{
int i, j;
R=_R; C=_C;
root=newNode2();
}
void update(int P, int Q, ll K)
{
int i, j;
P++; Q++;
update2(root, 1, R, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
int i, j;
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(int, int, int, int, ll)':
game.cpp:44:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'll query1(int, int, int, int, int)':
game.cpp:98:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'void update2(int, int, int, int, int, ll)':
game.cpp:114:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'll query2(int, int, int, int, int, int, int)':
game.cpp:140:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:151:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:151:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:158:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:158:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:165:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:165:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
