#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;
Node1() : val(0), lc(-1), rc(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
nodes1.push_back(Node1());
//printf("???%d %d %lld\n", nodes1.back().lc, nodes1.back().rc, nodes1.back().val);
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());
//printf("???%d %d %d\n", nodes2.back().lc, nodes2.back().rc, nodes2.back().val);
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(x<=mid)
{
if(nodes1[node].lc==-1) { int t=newNode1(); nodes1[node].lc=t; }
update1(nodes1[node].lc, tl, mid, x, val);
}
else
{
if(nodes1[node].rc==-1) { int t=newNode1(); nodes1[node].rc=t; }
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(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:45: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:67: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:83: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:109:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:120:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:120:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:127:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:127:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:134:9: warning: unused variable 'i' [-Wunused-variable]
int i, j;
^
game.cpp:134:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
380 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
380 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
256 KB |
Output is correct |
4 |
Correct |
872 ms |
17040 KB |
Output is correct |
5 |
Correct |
627 ms |
16844 KB |
Output is correct |
6 |
Correct |
751 ms |
14332 KB |
Output is correct |
7 |
Correct |
824 ms |
10328 KB |
Output is correct |
8 |
Correct |
538 ms |
9744 KB |
Output is correct |
9 |
Correct |
801 ms |
11036 KB |
Output is correct |
10 |
Correct |
716 ms |
9936 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
380 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
1525 ms |
14444 KB |
Output is correct |
13 |
Correct |
2741 ms |
7708 KB |
Output is correct |
14 |
Correct |
409 ms |
5640 KB |
Output is correct |
15 |
Correct |
3197 ms |
9528 KB |
Output is correct |
16 |
Correct |
310 ms |
17420 KB |
Output is correct |
17 |
Correct |
1235 ms |
14028 KB |
Output is correct |
18 |
Correct |
2176 ms |
19620 KB |
Output is correct |
19 |
Correct |
1834 ms |
23008 KB |
Output is correct |
20 |
Correct |
1703 ms |
22536 KB |
Output is correct |
21 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
2 |
Correct |
3 ms |
504 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
882 ms |
17176 KB |
Output is correct |
13 |
Correct |
618 ms |
16856 KB |
Output is correct |
14 |
Correct |
724 ms |
14428 KB |
Output is correct |
15 |
Correct |
822 ms |
10320 KB |
Output is correct |
16 |
Correct |
520 ms |
9704 KB |
Output is correct |
17 |
Correct |
795 ms |
10996 KB |
Output is correct |
18 |
Correct |
749 ms |
9976 KB |
Output is correct |
19 |
Correct |
1506 ms |
14568 KB |
Output is correct |
20 |
Correct |
2747 ms |
7964 KB |
Output is correct |
21 |
Correct |
408 ms |
5712 KB |
Output is correct |
22 |
Correct |
3182 ms |
9748 KB |
Output is correct |
23 |
Correct |
309 ms |
17548 KB |
Output is correct |
24 |
Correct |
1230 ms |
13916 KB |
Output is correct |
25 |
Correct |
2090 ms |
19544 KB |
Output is correct |
26 |
Correct |
1815 ms |
23024 KB |
Output is correct |
27 |
Correct |
1706 ms |
22680 KB |
Output is correct |
28 |
Correct |
1286 ms |
140424 KB |
Output is correct |
29 |
Runtime error |
3017 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
256 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
504 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
876 ms |
17200 KB |
Output is correct |
13 |
Correct |
622 ms |
16868 KB |
Output is correct |
14 |
Correct |
727 ms |
14392 KB |
Output is correct |
15 |
Correct |
814 ms |
10212 KB |
Output is correct |
16 |
Correct |
529 ms |
9732 KB |
Output is correct |
17 |
Correct |
769 ms |
10976 KB |
Output is correct |
18 |
Correct |
685 ms |
10064 KB |
Output is correct |
19 |
Correct |
1479 ms |
14528 KB |
Output is correct |
20 |
Correct |
2765 ms |
7688 KB |
Output is correct |
21 |
Correct |
408 ms |
5756 KB |
Output is correct |
22 |
Correct |
3202 ms |
9568 KB |
Output is correct |
23 |
Correct |
301 ms |
17484 KB |
Output is correct |
24 |
Correct |
1242 ms |
13892 KB |
Output is correct |
25 |
Correct |
2005 ms |
19508 KB |
Output is correct |
26 |
Correct |
1765 ms |
22960 KB |
Output is correct |
27 |
Correct |
1658 ms |
22544 KB |
Output is correct |
28 |
Correct |
1259 ms |
140540 KB |
Output is correct |
29 |
Runtime error |
2849 ms |
256004 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
30 |
Halted |
0 ms |
0 KB |
- |