oj.uz

Submission #793125

# Submission time Handle Problem Language Result Execution time Memory
793125 2023-07-25T14:11:53 Z poustouflan XORanges (eJOI19_xoranges) Python 3
55 / 100
 1000 ms 27272 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 11 ms 3028 KB Output is correct
2 Correct 11 ms 2976 KB Output is correct
3 Correct 11 ms 3028 KB Output is correct
4 Correct 11 ms 3040 KB Output is correct
5 Correct 11 ms 3036 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3064 KB Output is correct
2 Correct 17 ms 3016 KB Output is correct
3 Correct 14 ms 3060 KB Output is correct
4 Correct 13 ms 3028 KB Output is correct
5 Correct 14 ms 3052 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3028 KB Output is correct
2 Correct 11 ms 2976 KB Output is correct
3 Correct 11 ms 3028 KB Output is correct
4 Correct 11 ms 3040 KB Output is correct
5 Correct 11 ms 3036 KB Output is correct
6 Correct 14 ms 3064 KB Output is correct
7 Correct 17 ms 3016 KB Output is correct
8 Correct 14 ms 3060 KB Output is correct
9 Correct 13 ms 3028 KB Output is correct
10 Correct 14 ms 3052 KB Output is correct
11 Correct 38 ms 3548 KB Output is correct
12 Correct 38 ms 3632 KB Output is correct
13 Correct 52 ms 3556 KB Output is correct
14 Correct 40 ms 3664 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 27272 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3028 KB Output is correct
2 Correct 11 ms 2976 KB Output is correct
3 Correct 11 ms 3028 KB Output is correct
4 Correct 11 ms 3040 KB Output is correct
5 Correct 11 ms 3036 KB Output is correct
6 Correct 14 ms 3064 KB Output is correct
7 Correct 17 ms 3016 KB Output is correct
8 Correct 14 ms 3060 KB Output is correct
9 Correct 13 ms 3028 KB Output is correct
10 Correct 14 ms 3052 KB Output is correct
11 Correct 38 ms 3548 KB Output is correct
12 Correct 38 ms 3632 KB Output is correct
13 Correct 52 ms 3556 KB Output is correct
14 Correct 40 ms 3664 KB Output is correct
15 Execution timed out 1066 ms 27272 KB Time limit exceeded
16 Halted 0 ms 0 KB -