#include<bits/stdc++.h>
using namespace std;
const int MN = 100010;
int N, Q;
int A[MN], inva[MN];
vector<int> mrg(vector<int> &a, vector<int> &b) {
vector<int> ret;
int pos1 = 0, pos2 = 0;
while(pos1 < a.size() && pos2 < b.size()) {
if(a[pos1] < b[pos2]) ret.push_back(a[pos1++]);
else ret.push_back(b[pos2++]);
}
while(pos1 < a.size()) ret.push_back(a[pos1++]);
while(pos2 < b.size()) ret.push_back(b[pos2++]);
return ret;
}
struct BIT {
vector<int> tree;
void init() {
tree = vector<int>(4 * N, 0);
build(0, N - 1, 1);
}
void build(int l, int r, int n) {
if(l == r) {
tree[n] = A[l];
return;
}
int m = (l + r)>>1;
build(l, m, 2*n);
build(m + 1, r, 2*n + 1);
tree[n] = min(tree[2*n], tree[2*n + 1]);
}
vector<int> lquer(int idx, int l, int r, int n) {
if(idx < l || r < idx) return vector<int>();
vector<int> ret;
if(tree[n] == A[idx]) ret.push_back(l);
if(l == r) return ret;
int m = (l + r)>>1;
vector<int> L = lquer(idx, l, m, 2*n);
vector<int> R = lquer(idx, m + 1, r, 2*n + 1);
ret = mrg(ret, L);
ret = mrg(ret, R);
return ret;
}
vector<int> rquer(int idx, int l, int r, int n) {
if(idx < l || r < idx) return vector<int>();
vector<int> ret;
if(tree[n] == A[idx]) ret.push_back(r);
if(l == r) return ret;
int m = (l + r)>>1;
vector<int> L = rquer(idx, l, m, 2*n);
vector<int> R = rquer(idx, m + 1, r, 2*n + 1);
ret = mrg(ret, L);
ret = mrg(ret, R);
return ret;
}
vector<int> quer(int a, int b, int l, int r, int n) {
if(b < l || r < a) return vector<int>();
if(a <= l && r <= b) return vector<int>(1, tree[n]);
int m = (l + r)>>1;
vector<int> L = quer(a, b, l, m, 2*n);
vector<int> R = quer(a, b, m + 1, r, 2*n + 1);
return mrg(L, R);
}
} bit;
bool same(vector<int> &a, vector<int> b) {
if(a.size() != b.size()) return false;
for(int i = 0; i < a.size(); i++) if(a[i] != b[i]) return false;
return true;
}
int main() {
scanf("%d %d", &N, &Q);
for(int i = 0; i < N; i++) {
scanf("%d", &A[i]);
}
for(int i = 0; i < N; i++) inva[A[i]] = i;
bit.init();
for(int i = 0; i < Q; i++) {
int c; scanf("%d", &c);
vector<int> X(c);
int l = 1e9;
int r = -1e9;
for(int j = 0; j < c; j++) {
scanf("%d", &X[j]);
l = min(l, inva[ X[j] ]);
r = max(r, inva[ X[j] ]);
}
vector<int> L = bit.lquer(l, 0, N - 1, 1);
vector<int> R = bit.rquer(r, 0, N - 1, 1);
int p = -1;
int q = -1;
for(int j = 0; j < L.size(); j++) {
for(int k = 0; k < R.size(); k++) {
if(same(X, bit.quer(L[j], R[k], 0, N - 1, 1))) {
p = L[j];
q = R[k];
break;
}
}
}
if(p == -1) printf("-1\n");
else printf("%d %d\n", p + 1, q + 1);
}
}
Compilation message
easy.cpp: In function 'std::vector<int> mrg(std::vector<int>&, std::vector<int>&)':
easy.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos1 < a.size() && pos2 < b.size()) {
~~~~~^~~~~~~~~~
easy.cpp:12:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos1 < a.size() && pos2 < b.size()) {
~~~~~^~~~~~~~~~
easy.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos1 < a.size()) ret.push_back(a[pos1++]);
~~~~~^~~~~~~~~~
easy.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(pos2 < b.size()) ret.push_back(b[pos2++]);
~~~~~^~~~~~~~~~
easy.cpp: In function 'bool same(std::vector<int>&, std::vector<int>)':
easy.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < a.size(); i++) if(a[i] != b[i]) return false;
~~^~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:103:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < L.size(); j++) {
~~^~~~~~~~~~
easy.cpp:104:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int k = 0; k < R.size(); k++) {
~~^~~~~~~~~~
easy.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~~
easy.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
easy.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int c; scanf("%d", &c);
~~~~~^~~~~~~~~~
easy.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[j]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Correct |
| 2 |
Incorrect |
2 ms |
356 KB |
Wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
248 KB |
Correct |
| 2 |
Incorrect |
2 ms |
356 KB |
Wrong |
| 3 |
Halted |
0 ms |
0 KB |
- |
