Oto treść zadania:
Jankowi, dzięki intensywnym przygotowaniom, udało się dostać do finału OMJ. Oczywiście jako finalista Olimpiady umie już dodawać, więc w ramach przygotowań do finału wymyślił sobie nowe ćwiczenie: zapisuje na
kartce n liczb, a następnie wybiera dwie liczby całkowite a, b i oblicza XOR wszystkich zapisanych liczb od a-tej
do b-tej włącznie.
Niestety, finał OMJ został odwołany, więc Janek nie będzie miał możliwości sprawdzenia swoich umiejętności
na zawodach. Pomóż mu i napisz program obliczający poprawne odpowiedzi.
WEJŚCIE
W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n i q (1 ¬ n, q ¬ 106
) oznaczające odpowiednio
ile liczb zapisał Janek na kartce i ile pytań chce zadać.
W drugim wierszu znajduje się n liczb całkowitych z przedziału h0, 106
i – liczby zapisane przez Janka na kartce.
W każdym z następnych q wierszy znajdują się dwie liczby całkowite a i b (1 ¬ a ¬ b ¬ n), które oznaczają
odpowiednio numer pierwszej i ostatniej liczby przedziału, na którym należy policzyć XOR.
WYJŚCIE
Należy wypisać odpowiedzi na kolejne pytania Janka, każde w oddzielnej linii.
PRZYKŁAD
Wejście:
6 2
31 13 16 21 0 1
1 6
2 5
Wyjście:
22
8
Oto mój kod, który otrzymuje 40 punktów:
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int t[n];
for(int i = 0; i < n; i++){
cin >> t[i];
}
int sp[n];
sp[0] = t[0];
for(int i = 1; i < n; i++){
sp[i] = sp[i - 1] ^ t[i];
}
int a, b;
while(m--){
cin >> a >> b;
if(a == 1){
cout << sp[b-1] << endl;
}
else {
cout << (sp[b-1] ^ sp[a-2]) << endl;
}
}
}
Przekroczony został limit czasu. Czy ktoś pomógłby mi zoptymalizować kod?
Nie chodzi o to, że używam cout zamiast printf itp.