Submission #1070538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070538		horiaboeriu	XORanges (eJOI19_xoranges)	C++17	100 / 100	115 ms	8016 KiB

xoranges

#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 (stderr)

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 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25