oj.uz

Submission #793127

# Submission time Handle Problem Language Result Execution time Memory
793127 2023-07-25T14:12:49 Z poustouflan XORanges (eJOI19_xoranges) PyPy 3
100 / 100
 860 ms 46976 KB 
n, q = map(int, input().split())

A = list(map(int, input().split())) # scan results
A_pair = A[0::2]
A_impair = A[1::2]

prefixe = [0]
for x in A_pair:
    prefixe.append(x ^ prefixe[-1])
arbre_pair = []
for k in range(1, len(A_pair)+1):
    arbre_pair.append(
        prefixe[k] ^ prefixe[k-(k & (-k))]
    )

prefixe = [0]
for x in A_impair:
    prefixe.append(x ^ prefixe[-1])
arbre_impair = []
for k in range(1, len(A_impair)+1):
    arbre_impair.append(
        prefixe[k] ^ prefixe[k-(k & (-k))]
    )

def somme(k, arbre):
    # Somme k premiers elts
    s = 0
    while k >= 1:
        s ^= arbre[k-1]
        k -= k & (-k)
    return s

def ajouter(k, x, arbre):
    # Ajoute x en position k
    k += 1
    while k <= len(arbre):
        arbre[k-1] ^= x
        k += k & (-k)

def xorsum(l, r):
    assert l % 2 == r % 2

    if l % 2 == 0:
        # A_pair
        l = l // 2
        r = r // 2
        return somme(r+1, arbre_pair) ^ somme(l, arbre_pair)

    else:
        # A_impair
        l = l // 2
        r = r // 2
        return somme(r+1, arbre_impair) ^ somme(l, arbre_impair)

def set(i, j):
    if i % 2 == 0:
        # A_pair
        i = i // 2
        diff = A_pair[i] ^ j
        A_pair[i] = j
        ajouter(i, diff, arbre_pair)
    else:
        # A_impair
        i = i // 2
        diff = A_impair[i] ^ j
        A_impair[i] = j
        ajouter(i, diff, arbre_impair)




for _ in range(q):
    q, i, j = map(int, input().split())
    if q == 1:
        # rescan
        set(i-1, j)
    else:
        # query
        if (j - i) % 2 == 1:
            print(0)
        else:
            print(xorsum(i-1, j-1))

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 33 ms 18220 KB Output is correct
3 Correct 33 ms 18196 KB Output is correct
4 Correct 34 ms 18216 KB Output is correct
5 Correct 33 ms 18204 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 19372 KB Output is correct
2 Correct 56 ms 19804 KB Output is correct
3 Correct 51 ms 19172 KB Output is correct
4 Correct 56 ms 19220 KB Output is correct
5 Correct 49 ms 19240 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 33 ms 18220 KB Output is correct
3 Correct 33 ms 18196 KB Output is correct
4 Correct 34 ms 18216 KB Output is correct
5 Correct 33 ms 18204 KB Output is correct
6 Correct 59 ms 19372 KB Output is correct
7 Correct 56 ms 19804 KB Output is correct
8 Correct 51 ms 19172 KB Output is correct
9 Correct 56 ms 19220 KB Output is correct
10 Correct 49 ms 19240 KB Output is correct
11 Correct 149 ms 26756 KB Output is correct
12 Correct 151 ms 26792 KB Output is correct
13 Correct 138 ms 26776 KB Output is correct
14 Correct 143 ms 26276 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 852 ms 44636 KB Output is correct
2 Correct 776 ms 46480 KB Output is correct
3 Correct 771 ms 46484 KB Output is correct
4 Correct 788 ms 45692 KB Output is correct
5 Correct 736 ms 46472 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 18220 KB Output is correct
2 Correct 33 ms 18220 KB Output is correct
3 Correct 33 ms 18196 KB Output is correct
4 Correct 34 ms 18216 KB Output is correct
5 Correct 33 ms 18204 KB Output is correct
6 Correct 59 ms 19372 KB Output is correct
7 Correct 56 ms 19804 KB Output is correct
8 Correct 51 ms 19172 KB Output is correct
9 Correct 56 ms 19220 KB Output is correct
10 Correct 49 ms 19240 KB Output is correct
11 Correct 149 ms 26756 KB Output is correct
12 Correct 151 ms 26792 KB Output is correct
13 Correct 138 ms 26776 KB Output is correct
14 Correct 143 ms 26276 KB Output is correct
15 Correct 852 ms 44636 KB Output is correct
16 Correct 776 ms 46480 KB Output is correct
17 Correct 771 ms 46484 KB Output is correct
18 Correct 788 ms 45692 KB Output is correct
19 Correct 736 ms 46472 KB Output is correct
20 Correct 727 ms 46828 KB Output is correct
21 Correct 685 ms 46976 KB Output is correct
22 Correct 728 ms 46920 KB Output is correct
23 Correct 860 ms 46888 KB Output is correct
24 Correct 831 ms 46816 KB Output is correct