my-solutions/codeforces/round-923/task-d/main.cpp

86 lines
2.4 KiB
C++
Raw Permalink Normal View History

#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;
}
}