Task: | GCD queries |
Sender: | eax511 |
Submission time: | 2016-10-15 14:02:21 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | UNKNOWN | -- | details |
#2 | UNKNOWN | -- | details |
#3 | UNKNOWN | -- | details |
#4 | UNKNOWN | -- | details |
#5 | UNKNOWN | -- | details |
#6 | UNKNOWN | -- | details |
#7 | UNKNOWN | -- | details |
#8 | UNKNOWN | -- | details |
#9 | UNKNOWN | -- | details |
#10 | UNKNOWN | -- | details |
#11 | UNKNOWN | -- | details |
#12 | UNKNOWN | -- | details |
#13 | UNKNOWN | -- | details |
#14 | UNKNOWN | -- | details |
#15 | UNKNOWN | -- | details |
#16 | UNKNOWN | -- | details |
#17 | UNKNOWN | -- | details |
#18 | UNKNOWN | -- | details |
#19 | UNKNOWN | -- | details |
#20 | UNKNOWN | -- | details |
#21 | UNKNOWN | -- | details |
#22 | UNKNOWN | -- | details |
#23 | UNKNOWN | -- | details |
#24 | UNKNOWN | -- | details |
#25 | UNKNOWN | -- | details |
#26 | UNKNOWN | -- | details |
#27 | UNKNOWN | -- | details |
#28 | UNKNOWN | -- | details |
#29 | UNKNOWN | -- | details |
#30 | UNKNOWN | -- | details |
#31 | UNKNOWN | -- | details |
#32 | UNKNOWN | -- | details |
#33 | UNKNOWN | -- | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:25:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d",&n,&q); ^ input/code.cpp:27:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%d",st+N+i); ^ input/code.cpp:32:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result] scanf("%s %d %d",c,&x,&v); ^
Code
#include <stdio.h> #define N (1<<20) int st[N<<1]; int gcd(int a,int b){return b?gcd(b,a%b):a;} char c[1000]; void update(int a,int b){ int i = N+a; st[i]=b; for(;i>1;i>>=1)st[i>>1]=gcd(st[i],st[i^1]); } int query(int a,int b){ int i = N+a; int j = N+b; int ri = st[i]; int rj = st[j]; while((i>>1)!=(j>>1)){ if(~i&1)ri=gcd(st[i^1],ri); if(j&1)rj=gcd(st[j^1],rj); i>>=1,j>>=1; } return gcd(ri,rj); } int main(){ int n,q; scanf("%d %d",&n,&q); for(int i=0;i<n;++i){ scanf("%d",st+N+i); } for(int i=N-1;i>0;--i)st[i]=gcd(st[(i<<1)],st[(i<<1)+1]); for(int i=0;i<q;++i){ int x,v; scanf("%s %d %d",c,&x,&v); if(c[0]=='u')update(x-1,v); else printf("%d\n",query(x-1,v-1)); } return 0; }
Test details
Test 1
Verdict: UNKNOWN
input |
---|
10 10 706925441 321605763 203167195 ... |
correct output |
---|
1 1 223839214 1 110092684 ... |
user output |
---|
(not available) |
Test 2
Verdict: UNKNOWN
input |
---|
100000 10000 1 1 1 1 1 1 1 1 1 1 1 32 32 32... |
correct output |
---|
720 28800 11059200 7200 184320 ... |
user output |
---|
(not available) |
Test 3
Verdict: UNKNOWN
input |
---|
100000 100000 1 54 4860 4860 19440 933120 93... |
correct output |
---|
155520 7776000 25920 2880 194400000 ... |
user output |
---|
(not available) |
Test 4
Verdict: UNKNOWN
input |
---|
100000 100000 1 288 288 864 864 62208 186624... |
correct output |
---|
30720 3 737280 144000 3 ... |
user output |
---|
(not available) |
Test 5
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 10 2700 16200 162000 11340... |
correct output |
---|
34560 2 2 2 1 ... |
user output |
---|
(not available) |
Test 6
Verdict: UNKNOWN
input |
---|
100000 100000 1 1620 4536000 108864000 60963... |
correct output |
---|
43200 609638400 86400 241920 1 ... |
user output |
---|
(not available) |
Test 7
Verdict: UNKNOWN
input |
---|
100000 100000 1 3 3 3 90 68040 3402000 47628... |
correct output |
---|
29030400 1209600 5 1 2 ... |
user output |
---|
(not available) |
Test 8
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 72 3600 28800 31104000 124... |
correct output |
---|
2304000 2304000 2304000 691200 1152000 ... |
user output |
---|
(not available) |
Test 9
Verdict: UNKNOWN
input |
---|
100000 100000 1 2 2 2 18 1008 1008 2016 1209... |
correct output |
---|
1244160 1344 14515200 120960 103680 ... |
user output |
---|
(not available) |
Test 10
Verdict: UNKNOWN
input |
---|
100000 100000 1 7 42 17640 7056000 42336000 ... |
correct output |
---|
138240 1 60480000 9 1 ... |
user output |
---|
(not available) |
Test 11
Verdict: UNKNOWN
input |
---|
100000 100000 1 80 3840 19200 829440000 6635... |
correct output |
---|
1555200 6220800 4665600 995328000 18662400 ... |
user output |
---|
(not available) |
Test 12
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 5 300 27000 135000 1080000... |
correct output |
---|
2880000 151200 1440 34992000 120960000 ... |
user output |
---|
(not available) |
Test 13
Verdict: UNKNOWN
input |
---|
100000 100000 1 12 504 1512 36288 1016064 81... |
correct output |
---|
163296 254016 381024 7056 12700800 ... |
user output |
---|
(not available) |
Test 14
Verdict: UNKNOWN
input |
---|
100000 100000 1 7200 3499200 31492800 559872... |
correct output |
---|
8164800 2 576 2 1632960 ... |
user output |
---|
(not available) |
Test 15
Verdict: UNKNOWN
input |
---|
100000 100000 1 8 20160 483840 7741440 32514... |
correct output |
---|
1524096 82944 46448640 10368 2903040 ... |
user output |
---|
(not available) |
Test 16
Verdict: UNKNOWN
input |
---|
100000 100000 1 80 1600 96000 699840000 2332... |
correct output |
---|
3 36578304 116688600 10450944 3 ... |
user output |
---|
(not available) |
Test 17
Verdict: UNKNOWN
input |
---|
100000 100000 1 630 630 4410 31752000 362880... |
correct output |
---|
711244800 48384 227598336 3386880 2 ... |
user output |
---|
(not available) |
Test 18
Verdict: UNKNOWN
input |
---|
100000 100000 1 8 1440 1440 11520 34560 3456... |
correct output |
---|
2903040 40320 2257920 2520 60963840 ... |
user output |
---|
(not available) |
Test 19
Verdict: UNKNOWN
input |
---|
100000 100000 1 24 4032 4032 120960 4354560 ... |
correct output |
---|
17781120 51840 2540160 3628800 622080 ... |
user output |
---|
(not available) |
Test 20
Verdict: UNKNOWN
input |
---|
100000 100000 1 3645 127575 24494400 4898880... |
correct output |
---|
7776 1306368 92588832 1866240 163296 ... |
user output |
---|
(not available) |
Test 21
Verdict: UNKNOWN
input |
---|
100000 100000 1 10 20 40 80000 80000 2400000... |
correct output |
---|
18144 746496 489888 163296 24004512 ... |
user output |
---|
(not available) |
Test 22
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 90 3240 19440 1944000 2449... |
correct output |
---|
1134000 22680000 12600 12600 9 ... |
user output |
---|
(not available) |
Test 23
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 1 400 80000 80000 960000 8... |
correct output |
---|
62208000 12960000 17280 186624000 345600 ... |
user output |
---|
(not available) |
Test 24
Verdict: UNKNOWN
input |
---|
100000 100000 1 4 32 768 414720 58060800 870... |
correct output |
---|
4147200 82944 41472 12288 82944 ... |
user output |
---|
(not available) |
Test 25
Verdict: UNKNOWN
input |
---|
100000 100000 1 81 648 419904 6718464 362797... |
correct output |
---|
1680 2 8 1290240 8 ... |
user output |
---|
(not available) |
Test 26
Verdict: UNKNOWN
input |
---|
100000 100000 1 1 120 120 960 960 960 5760 6... |
correct output |
---|
28800 233280000 28800 28800 403200 ... |
user output |
---|
(not available) |
Test 27
Verdict: UNKNOWN
input |
---|
100000 100000 1 2352 37632 37632 790272 1896... |
correct output |
---|
6451200 2400 245760 34560 30720 ... |
user output |
---|
(not available) |
Test 28
Verdict: UNKNOWN
input |
---|
100000 100000 1 16 896 537600 37632000 26342... |
correct output |
---|
1 1 3317760 1 115200 ... |
user output |
---|
(not available) |
Test 29
Verdict: UNKNOWN
input |
---|
100000 100000 1 48 419904 1259712 357128352 ... |
correct output |
---|
21600 8640 1440 21600 21600 ... |
user output |
---|
(not available) |
Test 30
Verdict: UNKNOWN
input |
---|
100000 100000 1 32 7680 537600 5376000 37632... |
correct output |
---|
105840 241920 15120 18522000 24192 ... |
user output |
---|
(not available) |
Test 31
Verdict: UNKNOWN
input |
---|
4 3 2 4 6 3 q 1 4 q 1 3 q 3 4 |
correct output |
---|
1 2 3 |
user output |
---|
(not available) |
Test 32
Verdict: UNKNOWN
input |
---|
4 4 2 4 6 3 u 2 12 q 1 4 q 1 3 ... |
correct output |
---|
1 2 6 |
user output |
---|
(not available) |
Test 33
Verdict: UNKNOWN
input |
---|
1 3 1 q 1 1 u 1 2 q 1 1 |
correct output |
---|
1 2 |
user output |
---|
(not available) |