CSES - E4590 2016 5

CSES - E4590 2016 5 - Results

Submission details
Task:	GCD queries
Sender:	ivan
Submission time:	2016-10-15 14:20:12 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
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(int, char**)':
input/code.cpp:72:24: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
     while (n & (n - 1) != 0)
                        ^

Code

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 5;

int arr[4 * N];
int n, n_old, q;

int gcd(int a, int b) {
    if (a == -1) {
        return b;
    }

    if (b == -1) {
        return a;
    }

    if (a == 0) {
        return b;
    }

    if (a > b) {
        return gcd(b, a);
    }

    return gcd(b % a, a);
}

int range(int l, int r) {
    int res = -1;
    while (l < r) {
        if (l % 2 == 1) {
            res = gcd(res, arr[l]);
            ++l;
        }

        if (r % 2 == 0) {
            res = gcd(res, arr[r]);
            --r;
        }

        l /= 2;
        r /= 2;
    }

    if (l == r) {
        res = gcd(res, arr[l]);
    }

    return res;
}

void update(int i, int v) {
    int j = n + i;
    arr[j] = v;

    j = j / 2;

    while (j >= 1) {
        arr[j] = gcd(arr[2 * j], arr[2 * j + 1]);
        j = j / 2;
    }
}

int main(int argc, char *argv[])
{
    cin >> n_old >> q;
    n = n_old;

    while (n & (n - 1) != 0)
        n += 1;

    for (int i = 0; i < n_old; ++i) {
        cin >> arr[n + i];
    }

    for (int i = n_old; i < n; ++i) {
        arr[n + i] = -1;
    }

    for (int i = 2 * n - 1; i >= 2; --i) {
        if (arr[i / 2] == 0) {
            arr[i / 2] = arr[i];
        } else {
            arr[i / 2] = gcd(arr[i / 2], arr[i]);
        }
    }

//    for (int i = 0; i <= 2 * n - 1; ++i) {
//        cout << arr[i] << " ";
//    }
//    cout << endl;

    for (int i = 0; i < q; ++i) {
        char c = 'a';
        int l, r;
        cin >> c >> l >> r;

        if (c == 'q') {
            cout << range(n + l - 1, n + r - 1) << endl;
        } else {
            update(l - 1, r);
        }
    }

    return 0;
}

Test details

Test 1

Verdict: UNKNOWN

input
`10 10 706925441 321605763 203167195 ...` view save

correct output
`1 1 223839214 1 110092684 ...` view save

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

correct output
`720 28800 11059200 7200 184320 ...` view save

user output
(not available)

Test 3

Verdict: UNKNOWN

input
`100000 100000 1 54 4860 4860 19440 933120 93...` view save

correct output
`155520 7776000 25920 2880 194400000 ...` view save

user output
(not available)

Test 4

Verdict: UNKNOWN

input
`100000 100000 1 288 288 864 864 62208 186624...` view save

correct output
`30720 3 737280 144000 3 ...` view save

user output
(not available)

Test 5

Verdict: UNKNOWN

input
`100000 100000 1 1 10 2700 16200 162000 11340...` view save

correct output
`34560 2 2 2 1 ...` view save

user output
(not available)

Test 6

Verdict: UNKNOWN

input
`100000 100000 1 1620 4536000 108864000 60963...` view save

correct output
`43200 609638400 86400 241920 1 ...` view save

user output
(not available)

Test 7

Verdict: UNKNOWN

input
`100000 100000 1 3 3 3 90 68040 3402000 47628...` view save

correct output
`29030400 1209600 5 1 2 ...` view save

user output
(not available)

Test 8

Verdict: UNKNOWN

input
`100000 100000 1 1 72 3600 28800 31104000 124...` view save

correct output
`2304000 2304000 2304000 691200 1152000 ...` view save

user output
(not available)

Test 9

Verdict: UNKNOWN

input
`100000 100000 1 2 2 2 18 1008 1008 2016 1209...` view save

correct output
`1244160 1344 14515200 120960 103680 ...` view save

user output
(not available)

Test 10

Verdict: UNKNOWN

input
`100000 100000 1 7 42 17640 7056000 42336000 ...` view save

correct output
`138240 1 60480000 9 1 ...` view save

user output
(not available)

Test 11

Verdict: UNKNOWN

input
`100000 100000 1 80 3840 19200 829440000 6635...` view save

correct output
`1555200 6220800 4665600 995328000 18662400 ...` view save

user output
(not available)

Test 12

Verdict: UNKNOWN

input
`100000 100000 1 1 5 300 27000 135000 1080000...` view save

correct output
`2880000 151200 1440 34992000 120960000 ...` view save

user output
(not available)

Test 13

Verdict: UNKNOWN

input
`100000 100000 1 12 504 1512 36288 1016064 81...` view save

correct output
`163296 254016 381024 7056 12700800 ...` view save

user output
(not available)

Test 14

Verdict: UNKNOWN

input
`100000 100000 1 7200 3499200 31492800 559872...` view save

correct output
`8164800 2 576 2 1632960 ...` view save

user output
(not available)

Test 15

Verdict: UNKNOWN

input
`100000 100000 1 8 20160 483840 7741440 32514...` view save

correct output
`1524096 82944 46448640 10368 2903040 ...` view save

user output
(not available)

Test 16

Verdict: UNKNOWN

input
`100000 100000 1 80 1600 96000 699840000 2332...` view save

correct output
`3 36578304 116688600 10450944 3 ...` view save

user output
(not available)

Test 17

Verdict: UNKNOWN

input
`100000 100000 1 630 630 4410 31752000 362880...` view save

correct output
`711244800 48384 227598336 3386880 2 ...` view save

user output
(not available)

Test 18

Verdict: UNKNOWN

input
`100000 100000 1 8 1440 1440 11520 34560 3456...` view save

correct output
`2903040 40320 2257920 2520 60963840 ...` view save

user output
(not available)

Test 19

Verdict: UNKNOWN

input
`100000 100000 1 24 4032 4032 120960 4354560 ...` view save

correct output
`17781120 51840 2540160 3628800 622080 ...` view save

user output
(not available)

Test 20

Verdict: UNKNOWN

input
`100000 100000 1 3645 127575 24494400 4898880...` view save

correct output
`7776 1306368 92588832 1866240 163296 ...` view save

user output
(not available)

Test 21

Verdict: UNKNOWN

input
`100000 100000 1 10 20 40 80000 80000 2400000...` view save

correct output
`18144 746496 489888 163296 24004512 ...` view save

user output
(not available)

Test 22

Verdict: UNKNOWN

input
`100000 100000 1 1 90 3240 19440 1944000 2449...` view save

correct output
`1134000 22680000 12600 12600 9 ...` view save

user output
(not available)

Test 23

Verdict: UNKNOWN

input
`100000 100000 1 1 1 400 80000 80000 960000 8...` view save

correct output
`62208000 12960000 17280 186624000 345600 ...` view save

user output
(not available)

Test 24

Verdict: UNKNOWN

input
`100000 100000 1 4 32 768 414720 58060800 870...` view save

correct output
`4147200 82944 41472 12288 82944 ...` view save

user output
(not available)

Test 25

Verdict: UNKNOWN

input
`100000 100000 1 81 648 419904 6718464 362797...` view save

correct output
`1680 2 8 1290240 8 ...` view save

user output
(not available)

Test 26

Verdict: UNKNOWN

input
`100000 100000 1 1 120 120 960 960 960 5760 6...` view save

correct output
`28800 233280000 28800 28800 403200 ...` view save

user output
(not available)

Test 27

Verdict: UNKNOWN

input
`100000 100000 1 2352 37632 37632 790272 1896...` view save

correct output
`6451200 2400 245760 34560 30720 ...` view save

user output
(not available)

Test 28

Verdict: UNKNOWN

input
`100000 100000 1 16 896 537600 37632000 26342...` view save

correct output
`1 1 3317760 1 115200 ...` view save

user output
(not available)

Test 29

Verdict: UNKNOWN

input
`100000 100000 1 48 419904 1259712 357128352 ...` view save

correct output
`21600 8640 1440 21600 21600 ...` view save

user output
(not available)

Test 30

Verdict: UNKNOWN

input
`100000 100000 1 32 7680 537600 5376000 37632...` view save

correct output
`105840 241920 15120 18522000 24192 ...` view save

user output
(not available)

Test 31

Verdict: UNKNOWN

input
`4 3 2 4 6 3 q 1 4 q 1 3 q 3 4` view save

correct output
`1 2 3` view save

user output
(not available)

Test 32

Verdict: UNKNOWN

input
`4 4 2 4 6 3 u 2 12 q 1 4 q 1 3 ...` view save

correct output
`1 2 6` view save

user output
(not available)

Test 33

Verdict: UNKNOWN

input
`1 3 1 q 1 1 u 1 2 q 1 1` view save

correct output
`1 2` view save

user output
(not available)

E4590 2016 5

GCD queries

Compiler report

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

Tasks

Submissions (ivan)