86 lines
2.4 KiB
C++
86 lines
2.4 KiB
C++
|
#include <iostream>
|
||
|
|
|
||
|
|
using namespace std;
|
||
|
|
|
||
|
|
const int UNKN = -1;
|
||
|
|
const int NF = -2;
|
||
|
|
|
||
|
|
int main() {
|
||
|
|
int t;
|
||
|
|
cin >> t;
|
||
|
|
|
||
|
|
for (int y = 0; y < t; y++) {
|
||
|
|
int len;
|
||
|
|
cin >> len;
|
||
|
|
int* arr = new int[len];
|
||
|
|
int* cache = new int[len];
|
||
|
|
for (int i = 0; i < len; i++) {
|
||
|
|
cin >> arr[i];
|
||
|
|
cache[i] = UNKN;
|
||
|
|
}
|
||
|
|
|
||
|
|
int q_num;
|
||
|
|
cin >> q_num;
|
||
|
|
|
||
|
|
for (int v = 0; v < q_num; v++) {
|
||
|
|
int l, r;
|
||
|
|
cin >> l >> r;
|
||
|
|
l--;
|
||
|
|
r--;
|
||
|
|
|
||
|
|
if (cache[l] == NF) {
|
||
|
|
// Every number will be the same.
|
||
|
|
cout << "-1 -1" << endl;
|
||
|
|
} else if (cache[l] != UNKN) {
|
||
|
|
// Cache hit.
|
||
|
|
if (cache[l] > r) {
|
||
|
|
// Another number is beyond our range;
|
||
|
|
cout << "-1 -1" << endl;
|
||
|
|
} else {
|
||
|
|
// Answer was cached
|
||
|
|
cout << l + 1 << " " << cache[l] + 1 << endl;
|
||
|
|
}
|
||
|
|
} else {
|
||
|
|
bool found = false;
|
||
|
|
|
||
|
|
for (int i = l + 1; i <= r; i++) {
|
||
|
|
if (arr[i] != arr[l]) {
|
||
|
|
// Different number was found
|
||
|
|
cout << l+1 << " " << i+1 << endl;
|
||
|
|
found = true;
|
||
|
|
cache[l] = i;
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
|
||
|
|
if (cache[i] != UNKN) {
|
||
|
|
// CACHE HIT
|
||
|
|
if (cache[i] > r || cache[i] == NF) {
|
||
|
|
// Not found
|
||
|
|
break;
|
||
|
|
} else {
|
||
|
|
// Answer was cached
|
||
|
|
cout << l + 1 << " " << cache[i] + 1 << endl;
|
||
|
|
found = true;
|
||
|
|
cache[l] = cache[i];
|
||
|
|
break;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
if (!found) {
|
||
|
|
// Nothing was found
|
||
|
|
cout << "-1 -1" << endl;
|
||
|
|
if (r == len - 1) {
|
||
|
|
// If we reached the end of our array and nothing was found,
|
||
|
|
// remember this.
|
||
|
|
cache[l] = NF;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
delete[] cache;
|
||
|
|
delete[] arr;
|
||
|
|
}
|
||
|
|
}
|