#include<bits/stdc++.h>
using namespace std;
const int MN = 100010;
int N, Q;
int A[MN << 1], 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 tree[n]? vector<int>(1, tree[n]) : vector<int>();
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;
int p = 1;
while(p < N) p *= 2;
N = p;
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:107:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < L.size(); j++) {
~~^~~~~~~~~~
easy.cpp:108: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:91: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:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &X[j]);
~~~~~^~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Correct |
| 2 |
Correct |
3 ms |
356 KB |
Correct |
| 3 |
Correct |
3 ms |
560 KB |
Correct |
| 4 |
Correct |
83 ms |
592 KB |
Correct |
| 5 |
Correct |
13 ms |
592 KB |
Correct |
| 6 |
Correct |
119 ms |
768 KB |
Correct |
| 7 |
Correct |
108 ms |
1004 KB |
Correct |
| 8 |
Correct |
106 ms |
1004 KB |
Correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Correct |
| 2 |
Correct |
3 ms |
356 KB |
Correct |
| 3 |
Correct |
3 ms |
560 KB |
Correct |
| 4 |
Correct |
83 ms |
592 KB |
Correct |
| 5 |
Correct |
13 ms |
592 KB |
Correct |
| 6 |
Correct |
119 ms |
768 KB |
Correct |
| 7 |
Correct |
108 ms |
1004 KB |
Correct |
| 8 |
Correct |
106 ms |
1004 KB |
Correct |
| 9 |
Correct |
24 ms |
3664 KB |
Correct |
| 10 |
Correct |
247 ms |
3664 KB |
Correct |
| 11 |
Correct |
215 ms |
3664 KB |
Correct |
| 12 |
Correct |
429 ms |
3664 KB |
Correct |
| 13 |
Correct |
441 ms |
3664 KB |
Correct |
| 14 |
Correct |
455 ms |
3948 KB |
Correct |
| 15 |
Correct |
447 ms |
3968 KB |
Correct |
| 16 |
Correct |
449 ms |
3968 KB |
Correct |
| 17 |
Correct |
507 ms |
3968 KB |
Correct |
