#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
ll r, c, rr;
struct node{
int tl, tr;
ll val;
node *l = nullptr, *r = nullptr;
node(ll tlval, ll trval){
tl = tlval;
tr = trval;
val = 0;
}
node(){
tl = 0;
tr = rr-1;
val = 0;
}
void upd(ll idx, ll nv){
if(tl == idx && tr == idx){
val = nv;
return;
}
ll tm = (tl+tr)/2;
if(idx <= tm){
if(!l)
l = new node(tl, tm);
l->upd(idx, nv);
}
else{
if(!r)
r = new node(tm+1, tr);
r->upd(idx, nv);
}
ll xval = 0, yval = 0;
if(l)
xval = l->val;
if(r)
yval = r->val;
val = gcd2(xval, yval);
}
ll get(ll lef, ll rig){
if(tr < lef || rig < tl)
return 0;
if(lef <= tl && tr <= rig){
return val;
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(lef, rig);
if(r)
yval = r->get(lef, rig);
return gcd2(xval, yval);
}
};
struct seg{
int tl, tr;
node *val;
seg *l = nullptr, *r = nullptr;
map<int, node> v;
seg(ll tval, ll rval){
tl = tval;
tr = rval;
val = new node(0, c-1);
}
seg(){}
void upd(ll xidx, ll yidx, ll nv){
if(xidx < tl || xidx > tr) return;
v[yidx].upd(xidx, nv);
val->upd(yidx, v[yidx].val);
if(tl == tr){
return;
}
ll tm = (tl+tr)/2;
if(xidx <= tm){
if(!l)
l = new seg(tl, tm);
l->upd(xidx, yidx, nv);
}
else{
if(!r)
r = new seg(tm+1, tr);
r->upd(xidx, yidx, nv);
}
}
ll get(int xl, int xr, int yl, int yr){
if(tr < xl || xr < tl)
return 0;
if(xl <= tl && tr <= xr){
return val->get(yl, yr);
}
ll xval = 0, yval = 0;
if(l)
xval = l->get(xl, xr, yl, yr);
if(r)
yval = r->get(xl, xr, yl, yr);
return gcd2(xval, yval);
}
};
seg root;
void init(int R, int C) {
r = rr = R;
c = C;
root = seg(0, r-1);
}
void update(int P, int Q, long long K) {
root.upd(P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return root.get(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]
18 | int res;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
3 |
Correct |
2 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
288 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
0 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
256 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
784 ms |
28664 KB |
Output is correct |
5 |
Correct |
488 ms |
28792 KB |
Output is correct |
6 |
Correct |
704 ms |
26384 KB |
Output is correct |
7 |
Correct |
813 ms |
25848 KB |
Output is correct |
8 |
Correct |
488 ms |
15608 KB |
Output is correct |
9 |
Correct |
791 ms |
25976 KB |
Output is correct |
10 |
Correct |
750 ms |
25464 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
3 |
Correct |
2 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
1243 ms |
75000 KB |
Output is correct |
13 |
Correct |
1662 ms |
39416 KB |
Output is correct |
14 |
Correct |
342 ms |
2552 KB |
Output is correct |
15 |
Correct |
2005 ms |
53240 KB |
Output is correct |
16 |
Correct |
441 ms |
93432 KB |
Output is correct |
17 |
Correct |
1401 ms |
49912 KB |
Output is correct |
18 |
Correct |
2490 ms |
94200 KB |
Output is correct |
19 |
Correct |
2138 ms |
94132 KB |
Output is correct |
20 |
Correct |
2101 ms |
93340 KB |
Output is correct |
21 |
Correct |
1 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
3 |
Correct |
2 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
793 ms |
28664 KB |
Output is correct |
13 |
Correct |
480 ms |
28920 KB |
Output is correct |
14 |
Correct |
704 ms |
26088 KB |
Output is correct |
15 |
Correct |
881 ms |
25848 KB |
Output is correct |
16 |
Correct |
512 ms |
15736 KB |
Output is correct |
17 |
Correct |
801 ms |
25960 KB |
Output is correct |
18 |
Correct |
795 ms |
25748 KB |
Output is correct |
19 |
Correct |
1230 ms |
75000 KB |
Output is correct |
20 |
Correct |
1699 ms |
39708 KB |
Output is correct |
21 |
Correct |
369 ms |
2808 KB |
Output is correct |
22 |
Correct |
2005 ms |
53444 KB |
Output is correct |
23 |
Correct |
423 ms |
93572 KB |
Output is correct |
24 |
Correct |
1402 ms |
49912 KB |
Output is correct |
25 |
Correct |
2504 ms |
93988 KB |
Output is correct |
26 |
Correct |
2201 ms |
93960 KB |
Output is correct |
27 |
Correct |
2122 ms |
93356 KB |
Output is correct |
28 |
Runtime error |
481 ms |
256004 KB |
Execution killed with signal 9 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
2 ms |
768 KB |
Output is correct |
3 |
Correct |
2 ms |
768 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
1 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
768 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
1 ms |
768 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
512 KB |
Output is correct |
12 |
Correct |
767 ms |
28408 KB |
Output is correct |
13 |
Correct |
502 ms |
28156 KB |
Output is correct |
14 |
Correct |
729 ms |
25592 KB |
Output is correct |
15 |
Correct |
869 ms |
25336 KB |
Output is correct |
16 |
Correct |
521 ms |
15096 KB |
Output is correct |
17 |
Correct |
803 ms |
25592 KB |
Output is correct |
18 |
Correct |
801 ms |
25208 KB |
Output is correct |
19 |
Correct |
1326 ms |
74488 KB |
Output is correct |
20 |
Correct |
1734 ms |
39292 KB |
Output is correct |
21 |
Correct |
365 ms |
2424 KB |
Output is correct |
22 |
Correct |
2037 ms |
52984 KB |
Output is correct |
23 |
Correct |
423 ms |
93304 KB |
Output is correct |
24 |
Correct |
1438 ms |
49528 KB |
Output is correct |
25 |
Correct |
2495 ms |
93688 KB |
Output is correct |
26 |
Correct |
2215 ms |
93780 KB |
Output is correct |
27 |
Correct |
2105 ms |
93220 KB |
Output is correct |
28 |
Runtime error |
470 ms |
256004 KB |
Execution killed with signal 9 |
29 |
Halted |
0 ms |
0 KB |
- |