CSES - KILO 2017 4/5

Submission details
Task:	Coprime Queries
Sender:	Semikolonisti
Submission time:	2017-09-26 18:44:04 +0300
Language:	C++
Status:	READY
Result:	RUNTIME ERROR

Test results
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 ...` view save

correct output
`-1 2 -1 -1 -1` view save

user output
`-1 2 -1 -1 -1` view save

Test 2

Verdict: ACCEPTED

input
`5 5 88560 87945 59901 99630 83517 5 5 55350 1 5 64452 3 4 81549 ...` view save

correct output
`-1 -1 -1 -1 -1` view save

user output
`-1 -1 -1 -1 -1` view save

Test 3

Verdict: ACCEPTED

input
`100 100 21 21 105 10 231 10 2310 210 3...` view save

correct output
`-1 -1 80 -1 -1 ...` view save

user output
`-1 -1 80 -1 -1 ...` view save

Test 4

Verdict: ACCEPTED

input
`1000 1000 110 2310 1155 15 15 6 77 66 77...` view save

correct output
`-1 728 -1 -1 799 ...` view save

user output
`-1 728 -1 -1 799 ...` view save

Test 5

Verdict: ACCEPTED

input
`1 10 14 1 1 70 1 1 165 1 1 35 ...` view save

correct output
`-1 1 -1 -1 -1 ...` view save

user output
`-1 1 -1 -1 -1 ...` view save

Test 6

Verdict: ACCEPTED

input
`1 100000 15 1 1 1155 1 1 385 1 1 462 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
`-1 -1 -1 -1 -1 ...` view save

Test 7

Verdict: RUNTIME ERROR

input
`10000 10000 14 165 231 231 231 6 21 2310 7...` view save

correct output
`5859 -1 6545 -1 8357 ...` view save

user output
(empty)

Test 8

Verdict: RUNTIME ERROR

input
`100000 100000 6 462 231 10 42 33 210 21 165 ...` view save

correct output
`-1 68382 56540 62069 53256 ...` view save

user output
(empty)

Test 9

Verdict: ACCEPTED

input
`5 4 1 2 3 4 6 1 5 2 1 1 1 4 5 2 ...` view save

correct output
`3 1 -1 4` view save

user output
`3 1 -1 4` view save

Test 10

Verdict: RUNTIME ERROR

input
`100000 100000 18468 41472 41148 37908 90720 ...` view save

correct output
`77533 87593 87593 65504 35434 ...` view save

user output
(empty)

Test 11

Verdict: RUNTIME ERROR

input
`100000 100000 23976 66420 63504 63828 77436 ...` view save

correct output
`97877 91553 97877 31827 89348 ...` view save

user output
(empty)

Test 12

Verdict: RUNTIME ERROR

input
`100000 100000 27864 94284 89748 92340 65124 ...` view save

correct output
`86673 57805 -1 54513 85697 ...` view save

user output
(empty)

Test 13

Verdict: RUNTIME ERROR

input
`100000 100000 57996 69660 90072 25596 51840 ...` view save

correct output
`-1 44806 -1 44806 -1 ...` view save

user output
(empty)

Test 14

Verdict: RUNTIME ERROR

input
`100000 100000 61884 96228 15228 54108 38556 ...` view save

correct output
`-1 -1 -1 8255 -1 ...` view save

user output
(empty)

Test 15

Verdict: RUNTIME ERROR

input
`100000 100000 66096 20088 41148 81324 24948 ...` view save

correct output
`-1 -1 24063 -1 24063 ...` view save

user output
(empty)

Test 16

Verdict: RUNTIME ERROR

input
`100000 100000 51840 34992 42120 34344 11664 ...` view save

correct output
`-1 -1 -1 78028 78028 ...` view save

user output
(empty)

Test 17

Verdict: RUNTIME ERROR

input
`100000 100000 59616 60264 68364 62856 96552 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 18

Verdict: RUNTIME ERROR

input
`100000 100000 63504 84240 92016 90072 84240 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 19

Verdict: RUNTIME ERROR

input
`100000 100000 81648 21708 53784 4860 4212 36...` view save

correct output
`33649 -1 33649 33649 33649 ...` view save

user output
(empty)

Test 20

Verdict: RUNTIME ERROR

input
`100000 100000 84240 47952 78732 34668 89100 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 21

Verdict: RUNTIME ERROR

input
`100000 100000 90720 70632 3888 61884 76788 6...` view save

correct output
`55501 55501 55501 55501 -1 ...` view save

user output
(empty)

Test 22

Verdict: RUNTIME ERROR

input
`100000 100000 97674 41756 30587 93367 37814 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 23

Verdict: RUNTIME ERROR

input
`100000 100000 99864 80811 50662 89279 97747 ...` view save

correct output
`-1 90807 -1 -1 -1 ...` view save

user output
(empty)

Test 24

Verdict: RUNTIME ERROR

input
`100000 100000 89060 57159 57743 10585 95046 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 25

Verdict: RUNTIME ERROR

input
`100000 100000 4672 43581 39347 98842 25331 1...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 26

Verdict: RUNTIME ERROR

input
`100000 100000 69496 45260 9052 57451 85337 4...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 27

Verdict: RUNTIME ERROR

input
`100000 100000 71686 21681 16133 16060 45333 ...` view save

correct output
`80788 80788 80788 80788 80788 ...` view save

user output
(empty)

Test 28

Verdict: RUNTIME ERROR

input
`100000 100000 73073 59933 25769 86286 52998 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 29

Verdict: RUNTIME ERROR

input
`100000 100000 37960 36354 70153 44895 75628 ...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 30

Verdict: RUNTIME ERROR

input
`100000 100000 40223 38033 39858 3504 73000 7...` view save

correct output
`-1 -1 -1 -1 -1 ...` view save

user output
(empty)

Test 31

Verdict: RUNTIME ERROR

input
`100000 100000 11258 59490 22064 84827 23119 ...` view save

correct output
`99996 99996 100000 99996 99998 ...` view save

user output
(empty)

Test 32

Verdict: RUNTIME ERROR

input
`100000 100000 27387 84142 2618 47009 72373 7...` view save

correct output
`99996 99989 99996 99996 99997 ...` view save

user output
(empty)

Test 33

Verdict: RUNTIME ERROR

input
`100000 100000 10811 283 40068 76486 88923 53...` view save

correct output
`99996 99998 99995 99998 99998 ...` view save

user output
(empty)

Test 34

Verdict: RUNTIME ERROR

input
`100000 100000 62414 54744 92587 35574 44343 ...` view save

correct output
`54129 77561 57067 62241 77757 ...` view save

user output
(empty)

Test 35

Verdict: RUNTIME ERROR

input
`100000 100000 78542 3589 73140 21947 93596 2...` view save

correct output
`69504 84982 48765 92684 70335 ...` view save

user output
(empty)

Test 36

Verdict: RUNTIME ERROR

input
`100000 100000 94670 19729 53694 51425 18658 ...` view save

correct output
`17376 92059 91293 77274 87108 ...` view save

user output
(empty)

KILO 2017 4/5

Coprime Queries

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Tasks

Submissions (Semikolonisti)