#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
int N, Q;
int A[100010];
int L;
int val[1<<18];
int lv[1<<18], rv[1<<18];
vector <int> idxs[100010];
int wc[100010];
int is_last(int x) {
++x; if((x&-x) == x) return 1;
return 0;
}
int is_first(int x) {
if((x&-x) == x) return 1;
return 0;
}
int travel_to_right(vector <int> &X, int i, int rt) {
if(i == szz(X) - 1) return rv[rt] > N ? -1 : rv[rt];
if(is_last(rt)) return -1;
int nxt = 2 * rt + 2;
while(nxt < 2 * L && val[nxt] == X[i + 1]) {
int temp = travel_to_right(X, i + 1, nxt);
if(temp != -1) return temp;
nxt *= 2;
}
return -1;
}
int travel_to_left(vector <int> &X, int i, int rt) {
if(i == 0) return lv[rt];
if(is_first(rt)) return -1;
int nxt = 2 * rt - 1;
while(nxt < 2 * L && val[nxt] == X[i - 1]) {
int temp = travel_to_left(X, i - 1, nxt);
if(temp != -1) return temp;
nxt = nxt * 2 + 1;
}
return -1;
}
pii chk(vector <int> &X, int i, int rt) {
if(i > 0 && !is_first(rt) && rt % 2 == 0 && val[rt - 1] == X[i - 1]) {
int rv = travel_to_right(X, i, rt);
int lv = travel_to_left(X, i - 1, rt - 1);
if(rv != -1 && lv != -1) return pii(lv, rv);
}
int rv = travel_to_right(X, i, rt);
if(rv == -1) return pii(-1, -1);
int lv = travel_to_left(X, i, rt);
if(lv == -1) return pii(-1, -1);
return pii(lv, rv);
}
void query(vector <int> X) {
sort(all(X), [&](int x, int y) { return wc[x] < wc[y]; });
rep(i, szz(X)) {
int me = X[i];
for(int rt : idxs[me]) {
pii t = chk(X, i, rt);
if(t.Fi != -1) {
printf("%d %d\n", t.Fi, t.Se);
return;
}
}
}
puts("-1");
}
int main() {
scanf("%d%d", &N, &Q);
for(int i=1;i<=N;i++) scanf("%d", A + i);
for(int i=1;i<=N;i++) wc[A[i]] = i;
L = 1;
while(L < N) L *= 2;
for(int i=1;i<=N;i++) {
val[i + L - 1] = A[i];
}
for(int i=N+1;i<=L;i++) val[i+L-1] = 1e9;
for(int i=L-1;i;i--) val[i] = min(val[i*2], val[i*2+1]);
for(int i=L;i<2*L;i++) lv[i] = rv[i] = i - L + 1;
for(int i=L-1;i;i--) lv[i] = lv[i*2], rv[i] = rv[i*2+1];
for(int i=1;i<2*L;i++) if(rv[i] <= N) idxs[val[i]].pb(i);
for(int i=1;i<=Q;i++) {
int c; scanf("%d", &c);
vector <int> v;
rep(j, c) {
int x; scanf("%d", &x);
v.pb(x);
}
query(v);
}
return 0;
}
Compilation message
easy.cpp: In function 'int main()':
easy.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
easy.cpp:103:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;i++) scanf("%d", A + i);
~~~~~^~~~~~~~~~~~~
easy.cpp:116:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int c; scanf("%d", &c);
~~~~~^~~~~~~~~~
easy.cpp:119:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x; scanf("%d", &x);
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2684 KB |
Correct |
| 2 |
Correct |
5 ms |
2788 KB |
Correct |
| 3 |
Incorrect |
5 ms |
2864 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
2684 KB |
Correct |
| 2 |
Correct |
5 ms |
2788 KB |
Correct |
| 3 |
Incorrect |
5 ms |
2864 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
