oj.uz

Submission #1070538

# Submission time Handle Problem Language Result Execution time Memory
1070538 2024-08-22T15:08:31 Z horiaboeriu XORanges (eJOI19_xoranges) C++17
100 / 100
 115 ms 8016 KB 
#include <bits/stdc++.h>

using namespace std;
#define MAXN 200000
int v[MAXN + 1], aibi[MAXN / 2 + 1], aibp[MAXN / 2 + 1];//aib pentru xor
void addBit(int poz, int n, int val, int aib[]) {
    while (poz <= n) {
        aib[poz] ^= val;
        poz += (poz & (-poz));
    }
}
int bitXor(int poz, int aib[]) {
    int s;
    s = 0;
    while (poz > 0) {
        s ^= aib[poz];
        poz &= (poz - 1);
    }
    return s;
}
int main()
{
    //in intervalul de la st la dr, fiecarui numar i se va face xor de (cate nr are in stanga + 1) * (cate nr are in dreapta + 1)
    //ca un interval care il contine poate incepe la orice pozitie <= cu el si la oricare >= cu el
    //daca in interval sunt x numere si x este par, atunci
    //primul numar apare de 1 * x, al doilea de 2 * (x - 1), urmatoarele de
    //3 * (x - 2), 4 * (x - 3), 5 * (x - 4)... si din cei doi termeni care se inmultesc, unul sigur este par ca trebuie sa aiba suma x + 1, deci unul e par si altul imapr
    //deci fiecare numar apare de un numar par de ori deci xorul intervalului va fi 0 ca se elimina fiecare

    //daca x este impar, atunci, cei doi termeni inmultiti vor avea suma x + 1 care este para
    //cei de pe poz impare vor avea nr in stanga + 1 = impar, nr in dreapta + 1 = impar, deci fac xorul de pe poz impare, daca prima poz este st
    //fac cu aib in loc de aint
    int n, q, i, nri, nrp, cer, p, x, st, dr;
    scanf("%d%d", &n, &q);
    nri = (n + 1) / 2;
    nrp = n / 2;
    for (i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        if (i % 2 == 0) {
            addBit(i / 2, nrp, v[i], aibp);
        } else {
            addBit(i / 2 + 1, nri, v[i], aibi);
        }
    }
    for (i = 0; i < q; i++) {
        scanf("%d", &cer);
        if (cer == 1) {
            scanf("%d%d", &p, &x);
            //voi actualiza cu xorul dintre x si v[p] ca toate v[p] sa se transforme in x
            if (p % 2 == 0) {
                addBit(p / 2, nrp, x ^ v[p], aibp);
            } else {
                addBit(p / 2 + 1, nri, x ^ v[p], aibi);
            }
            v[p] = x;
        } else {
            scanf("%d%d", &st, &dr);
            if ((dr - st + 1) % 2 == 0) {
                printf("0\n");
            } else {
                if (st % 2 > 0) {
                    printf("%d\n", bitXor(st / 2, aibi) ^ bitXor(dr / 2 + 1, aibi));
                } else {
                    printf("%d\n", bitXor((st - 2) / 2, aibp) ^ bitXor(dr / 2, aibp));
                }
            }
        }
    }
    return 0;
}

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
xoranges.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~
xoranges.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d", &cer);
      |         ~~~~~^~~~~~~~~~~~
xoranges.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |             scanf("%d%d", &p, &x);
      |             ~~~~~^~~~~~~~~~~~~~~~
xoranges.cpp:57:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |             scanf("%d%d", &st, &dr);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 444 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 7836 KB Output is correct
2 Correct 65 ms 7852 KB Output is correct
3 Correct 83 ms 8016 KB Output is correct
4 Correct 61 ms 7528 KB Output is correct
5 Correct 62 ms 7508 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 2 ms 580 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 66 ms 7836 KB Output is correct
16 Correct 65 ms 7852 KB Output is correct
17 Correct 83 ms 8016 KB Output is correct
18 Correct 61 ms 7528 KB Output is correct
19 Correct 62 ms 7508 KB Output is correct
20 Correct 65 ms 7508 KB Output is correct
21 Correct 83 ms 7720 KB Output is correct
22 Correct 115 ms 7732 KB Output is correct
23 Correct 62 ms 7660 KB Output is correct
24 Correct 75 ms 7508 KB Output is correct