Task: | GCD queries |
Sender: | HopeICanCode |
Submission time: | 2016-10-15 14:51:42 +0300 |
Language: | C++ |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
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 <bits/stdc++.h> #define UNVISITED -1 #define BIGINT 1 << 25 #define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(15); using namespace std; typedef long long int64; typedef pair<int, int> ii; vector<int> num; int gcd(int a, int b){ while(b > 0){ int temp = b; b = a % b; a = temp; } return a; } int gcdList(int a, int b){ if(a == b) return num[a]; int mid = (a + b) / 2; int gcdA = gcdList(a, mid); int gcdB = gcdList(mid + 1, b); return gcd(gcdA, gcdB); } int main(){ _ int n, q; cin >> n >> q; num.assign(n + 1, 0); for(int i = 1; i <= n; ++i) cin >> num[i]; char op; int a, b; for(int i = 0; i < q; ++i){ cin >> op >> a >> b; if(op == 'u') num[a] = b; else { cout << gcdList(a, b) << endl; } } 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) |