Task: | GCD queries |
Sender: | Pohjantahti |
Submission time: | 2018-10-20 13:40:32 +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 |
Code
#include <iostream> using namespace std; const int N = (1<<18); int n, q; int st[2*N]; int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } void muuta(int k, int x) { k += N; st[k] = x; for (k /= 2; k >= 1; k /= 2) { st[k] = gcd(st[2*k], st[2*k+1]); } } int range_gcd(int a, int b) { a += N; b += N; int cres = st[a]; while (a <= b) { if (a%2 == 1) { cres = gcd(cres, st[a++]); } if (b%2 == 0) { cres = gcd(cres, st[b--]); } a /= 2; b /= 2; } return cres; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> q; for (int i = 1; i <= n; ++i) { int cx; cin >> cx; muuta(i, cx); } for (int cq = 0; cq < q; ++cq) { char tp; cin >> tp; if (tp == 'u') { int k, x; cin >> k >> x; muuta(k, x); } else { int l, r; cin >> l >> r; cout << range_gcd(l, r) << "\n"; } } 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) |