#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXQ 22005
#define orta ((bas+son)/2)
long long gcd2(long long X, long long Y) {
if(X<Y) swap(X,Y);
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SEG2 {
int L,R;
ll GCD;
} S2[MAXQ*32*32];
struct SEG1 {
int U,D;
int SG2;
} S1[MAXQ*32];
int total2,total1,R,C;
ll get2(int node,int bas,int son,int Q,int V) {
if(bas>V || son<Q) return 0;
if(bas>=Q && son<=V) return S2[node].GCD;
return gcd2(get2(S2[node].L,bas,orta,Q,V),get2(S2[node].R,orta+1,son,Q,V));
}
ll get1(int node,int bas,int son,int P,int Q,int U,int V) {
if(bas>P || son<Q) return 0;
if(bas>=P && son<=U) {
if(!S1[node].SG2) return 0;
return get2(S1[node].SG2,0,C-1,Q,V);
}
return gcd2(get1(S1[node].U,bas,orta,P,Q,U,V),get1(S1[node].D,orta+1,son,P,Q,U,V));
}
void up2(int node,int bas,int son,int Q,ll K) {
if(bas>Q || son<Q) return ;
if(bas==Q && son==Q) {
S2[node].GCD=K;
return ;
}
if(!S2[node].L) {
total2++;
S2[node].L=total2;
}
if(!S2[node].R) {
total2++;
S2[node].R=total2;
}
up2(S2[node].L,bas,orta,Q,K);
up2(S2[node].R,orta+1,son,Q,K);
S2[node].GCD=gcd2(S2[S2[node].L].GCD,S2[S2[node].R].GCD);
}
void up1(int node,int bas,int son,int P,int Q,ll K) {
if(bas>P || son<P) return ;
if(bas==P && son==P) {
if(!S1[node].SG2) {
total2++;
S1[node].SG2=total2;
}
up2(S1[node].SG2,0,C-1,Q,K);
return ;
}
if(!S1[node].U) {
total1++;
S1[node].U=total1;
}
if(!S1[node].D) {
total1++;
S1[node].D=total1;
}
up1(S1[node].U,bas,orta,P,Q,K);
up1(S1[node].D,orta+1,son,P,Q,K);
if(!S1[node].SG2) {
total2++;
S1[node].SG2=total2;
}
K=gcd2(get2(S1[S1[node].U].SG2,0,C-1,Q,Q),get2(S1[S1[node].D].SG2,0,C-1,Q,Q));
up2(S1[node].SG2,0,C-1,Q,K);
}
void init(int R, int C) {
total1=1;
::R=R;
::C=C;
}
void update(int P, int Q, long long K) {
up1(1,0,R-1,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
return get1(1,0,R-1,P,Q,U,V);
}
/*
#include <stdio.h>
#include <stdlib.h>
#include "game.h"
#define fail(s, x...) do { \
fprintf(stderr, s "\n", ## x); \
exit(1); \
} while(0)
#define MAX_SIZE 1000000000
#define MAX_N 272000
int main() {
int R, C, N;
int P, Q, U, V;
long long K;
int i, type;
int res;
FILE *f = fopen("game.in", "r");
if (!f)
fail("Failed to open input file.");
res = fscanf(f, "%d", &R);
res = fscanf(f, "%d", &C);
res = fscanf(f, "%d", &N);
init(R, C);
for (i = 0; i < N; i++) {
res = fscanf(f, "%d", &type);
if (type == 1) {
res = fscanf(f, "%d%d%lld", &P, &Q, &K);
update(P, Q, K);
} else if (type == 2) {
res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
printf("QUERY----> %lld\n", calculate(P, Q, U, V));
} else
fail("Invalid action type in input file.");
}
fclose(f);
return 0;
}
*/
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;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Runtime error |
766 ms |
257024 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
257024 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
