Task: | Coprime Queries |
Sender: | Semikolonisti |
Submission time: | 2017-09-26 18:44:04 +0300 |
Language: | C++ |
Status: | READY |
Result: | RUNTIME ERROR |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.17 s | details |
#4 | ACCEPTED | 1.54 s | details |
#5 | ACCEPTED | 0.05 s | details |
#6 | ACCEPTED | 0.15 s | details |
#7 | RUNTIME ERROR | 1.81 s | details |
#8 | RUNTIME ERROR | 2.59 s | details |
#9 | ACCEPTED | 0.04 s | details |
#10 | RUNTIME ERROR | 2.74 s | details |
#11 | RUNTIME ERROR | 2.72 s | details |
#12 | RUNTIME ERROR | 2.79 s | details |
#13 | RUNTIME ERROR | 2.33 s | details |
#14 | RUNTIME ERROR | 2.65 s | details |
#15 | RUNTIME ERROR | 2.51 s | details |
#16 | RUNTIME ERROR | 2.65 s | details |
#17 | RUNTIME ERROR | 2.71 s | details |
#18 | RUNTIME ERROR | 2.49 s | details |
#19 | RUNTIME ERROR | 2.71 s | details |
#20 | RUNTIME ERROR | 2.67 s | details |
#21 | RUNTIME ERROR | 2.56 s | details |
#22 | RUNTIME ERROR | 2.65 s | details |
#23 | RUNTIME ERROR | 2.35 s | details |
#24 | RUNTIME ERROR | 2.51 s | details |
#25 | RUNTIME ERROR | 2.81 s | details |
#26 | RUNTIME ERROR | 2.65 s | details |
#27 | RUNTIME ERROR | 2.59 s | details |
#28 | RUNTIME ERROR | 2.61 s | details |
#29 | RUNTIME ERROR | 2.55 s | details |
#30 | RUNTIME ERROR | 2.62 s | details |
#31 | RUNTIME ERROR | 2.23 s | details |
#32 | RUNTIME ERROR | 2.54 s | details |
#33 | RUNTIME ERROR | 2.25 s | details |
#34 | RUNTIME ERROR | 2.67 s | details |
#35 | RUNTIME ERROR | 2.06 s | details |
#36 | RUNTIME ERROR | 2.78 s | details |
Code
#include <bits/stdc++.h> #define ll long long #define pii pair<int, int> #define N (1<<17) using namespace std; /* Lollero ei tuu menee läpi :Dddd mut pakko yrittää */ int p[100001]; int ch[100000]; set<int> s[10000]; vector<int> ps; int v[100000]; int main () { cin.tie(0); cin.sync_with_stdio(false); int n, q; cin>>n>>q; for (int i = 0; i < n; i++) { cin>>v[i]; } for (int i = 2; i <= 100000; i++) { if (p[i]) continue; for (int j = 2 * i; j <= 100000; j += i) { p[j] = 1; } ch[i] = ps.size(); ps.push_back(i); } for (int i : ps) { for (int j = 0; j < n; j++) { if (v[j] % i) s[ch[i]].insert(j); } } for (int i = 0; i < q; i++) { int l, r, x; cin>>l>>r>>x; vector<int> d; for (int j = 2; j * j <= x; j++) { if (x % j == 0) d.push_back(ch[j]); while (x % j == 0) { x /= j; } } if (x != 1) d.push_back(ch[x]); int ans = -1; int p = l - 1; while (p <= r - 1) { bool q = true; for (int k : d) { auto a = s[k].lower_bound(p); if (a != s[k].end()) { if (*a != p) { p = *a; q = false; break; } } else { p = r; q = false; break; } } if (q) { ans = p + 1; p++; } } cout<<ans<<endl; } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
5 5 231 35 385 30 385 5 5 110 1 2 6 3 3 22 ... |
correct output |
---|
-1 2 -1 -1 -1 |
user output |
---|
-1 2 -1 -1 -1 |
Test 2
Verdict: ACCEPTED
input |
---|
5 5 88560 87945 59901 99630 83517 5 5 55350 1 5 64452 3 4 81549 ... |
correct output |
---|
-1 -1 -1 -1 -1 |
user output |
---|
-1 -1 -1 -1 -1 |
Test 3
Verdict: ACCEPTED
input |
---|
100 100 21 21 105 10 231 10 2310 210 3... |
correct output |
---|
-1 -1 80 -1 -1 ... |
user output |
---|
-1 -1 80 -1 -1 ... |
Test 4
Verdict: ACCEPTED
input |
---|
1000 1000 110 2310 1155 15 15 6 77 66 77... |
correct output |
---|
-1 728 -1 -1 799 ... |
user output |
---|
-1 728 -1 -1 799 ... |
Test 5
Verdict: ACCEPTED
input |
---|
1 10 14 1 1 70 1 1 165 1 1 35 ... |
correct output |
---|
-1 1 -1 -1 -1 ... |
user output |
---|
-1 1 -1 -1 -1 ... |
Test 6
Verdict: ACCEPTED
input |
---|
1 100000 15 1 1 1155 1 1 385 1 1 462 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
-1 -1 -1 -1 -1 ... |
Test 7
Verdict: RUNTIME ERROR
input |
---|
10000 10000 14 165 231 231 231 6 21 2310 7... |
correct output |
---|
5859 -1 6545 -1 8357 ... |
user output |
---|
(empty) |
Test 8
Verdict: RUNTIME ERROR
input |
---|
100000 100000 6 462 231 10 42 33 210 21 165 ... |
correct output |
---|
-1 68382 56540 62069 53256 ... |
user output |
---|
(empty) |
Test 9
Verdict: ACCEPTED
input |
---|
5 4 1 2 3 4 6 1 5 2 1 1 1 4 5 2 ... |
correct output |
---|
3 1 -1 4 |
user output |
---|
3 1 -1 4 |
Test 10
Verdict: RUNTIME ERROR
input |
---|
100000 100000 18468 41472 41148 37908 90720 ... |
correct output |
---|
77533 87593 87593 65504 35434 ... |
user output |
---|
(empty) |
Test 11
Verdict: RUNTIME ERROR
input |
---|
100000 100000 23976 66420 63504 63828 77436 ... |
correct output |
---|
97877 91553 97877 31827 89348 ... |
user output |
---|
(empty) |
Test 12
Verdict: RUNTIME ERROR
input |
---|
100000 100000 27864 94284 89748 92340 65124 ... |
correct output |
---|
86673 57805 -1 54513 85697 ... |
user output |
---|
(empty) |
Test 13
Verdict: RUNTIME ERROR
input |
---|
100000 100000 57996 69660 90072 25596 51840 ... |
correct output |
---|
-1 44806 -1 44806 -1 ... |
user output |
---|
(empty) |
Test 14
Verdict: RUNTIME ERROR
input |
---|
100000 100000 61884 96228 15228 54108 38556 ... |
correct output |
---|
-1 -1 -1 8255 -1 ... |
user output |
---|
(empty) |
Test 15
Verdict: RUNTIME ERROR
input |
---|
100000 100000 66096 20088 41148 81324 24948 ... |
correct output |
---|
-1 -1 24063 -1 24063 ... |
user output |
---|
(empty) |
Test 16
Verdict: RUNTIME ERROR
input |
---|
100000 100000 51840 34992 42120 34344 11664 ... |
correct output |
---|
-1 -1 -1 78028 78028 ... |
user output |
---|
(empty) |
Test 17
Verdict: RUNTIME ERROR
input |
---|
100000 100000 59616 60264 68364 62856 96552 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 18
Verdict: RUNTIME ERROR
input |
---|
100000 100000 63504 84240 92016 90072 84240 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 19
Verdict: RUNTIME ERROR
input |
---|
100000 100000 81648 21708 53784 4860 4212 36... |
correct output |
---|
33649 -1 33649 33649 33649 ... |
user output |
---|
(empty) |
Test 20
Verdict: RUNTIME ERROR
input |
---|
100000 100000 84240 47952 78732 34668 89100 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 21
Verdict: RUNTIME ERROR
input |
---|
100000 100000 90720 70632 3888 61884 76788 6... |
correct output |
---|
55501 55501 55501 55501 -1 ... |
user output |
---|
(empty) |
Test 22
Verdict: RUNTIME ERROR
input |
---|
100000 100000 97674 41756 30587 93367 37814 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 23
Verdict: RUNTIME ERROR
input |
---|
100000 100000 99864 80811 50662 89279 97747 ... |
correct output |
---|
-1 90807 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 24
Verdict: RUNTIME ERROR
input |
---|
100000 100000 89060 57159 57743 10585 95046 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 25
Verdict: RUNTIME ERROR
input |
---|
100000 100000 4672 43581 39347 98842 25331 1... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 26
Verdict: RUNTIME ERROR
input |
---|
100000 100000 69496 45260 9052 57451 85337 4... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 27
Verdict: RUNTIME ERROR
input |
---|
100000 100000 71686 21681 16133 16060 45333 ... |
correct output |
---|
80788 80788 80788 80788 80788 ... |
user output |
---|
(empty) |
Test 28
Verdict: RUNTIME ERROR
input |
---|
100000 100000 73073 59933 25769 86286 52998 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 29
Verdict: RUNTIME ERROR
input |
---|
100000 100000 37960 36354 70153 44895 75628 ... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 30
Verdict: RUNTIME ERROR
input |
---|
100000 100000 40223 38033 39858 3504 73000 7... |
correct output |
---|
-1 -1 -1 -1 -1 ... |
user output |
---|
(empty) |
Test 31
Verdict: RUNTIME ERROR
input |
---|
100000 100000 11258 59490 22064 84827 23119 ... |
correct output |
---|
99996 99996 100000 99996 99998 ... |
user output |
---|
(empty) |
Test 32
Verdict: RUNTIME ERROR
input |
---|
100000 100000 27387 84142 2618 47009 72373 7... |
correct output |
---|
99996 99989 99996 99996 99997 ... |
user output |
---|
(empty) |
Test 33
Verdict: RUNTIME ERROR
input |
---|
100000 100000 10811 283 40068 76486 88923 53... |
correct output |
---|
99996 99998 99995 99998 99998 ... |
user output |
---|
(empty) |
Test 34
Verdict: RUNTIME ERROR
input |
---|
100000 100000 62414 54744 92587 35574 44343 ... |
correct output |
---|
54129 77561 57067 62241 77757 ... |
user output |
---|
(empty) |
Test 35
Verdict: RUNTIME ERROR
input |
---|
100000 100000 78542 3589 73140 21947 93596 2... |
correct output |
---|
69504 84982 48765 92684 70335 ... |
user output |
---|
(empty) |
Test 36
Verdict: RUNTIME ERROR
input |
---|
100000 100000 94670 19729 53694 51425 18658 ... |
correct output |
---|
17376 92059 91293 77274 87108 ... |
user output |
---|
(empty) |