#include<bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
int N, Q;
int arr[2*MAXN];
int L[2*MAXN];
int R[2*MAXN];
vector<int> idx[MAXN];
void add(vector<int>& interv, int na)
{
while(R[na] >= N){
if(arr[na] == arr[2*na]) na = 2*na;
else na = 2*na+1;
}
for(auto& y: interv)
{
while(L[na] <= L[y] && R[y] <= R[na])
{
if(arr[na] == arr[2*na]) na = 2*na;
else na = 2*na+1;
}
}
interv.push_back(na);
}
pair<int, int> verify(vector<int> interv)
{
vector<int> ans;
int s = MAXN, e = 0;
for(auto x: interv) s = min(s, L[x]), e = max(e, R[x]);
int rs = s, re = e;
s += MAXN; e += MAXN;
while (s <= e)
{
if(s%2 == 1)
ans.push_back(s++);
if(e%2 == 0)
ans.push_back(e--);
s /= 2; e /= 2;
}
sort(ans.begin(), ans.end());
sort(interv.begin(), interv.end());
if(ans == interv) return make_pair(rs, re);
else return make_pair(-1, -1);
}
/*
pair<int, int> verify(vector<int> interv)
{
sort(interv.begin(), interv.end(),
[](int a, int b){ return L[a] < L[b]; });
for(int i=0; i<(int)interv.size()-1; ++i)
{
int lv = interv[i], rv = interv[i+1];
if(R[lv]+1 != L[rv]) return make_pair(-1, -1);
if(lv+1 == rv && lv%2==0) return make_pair(-1, -1);
}
return make_pair(L[interv[0]], R[interv.back()]);
}
*/
pair<int, int> solve(vector<int> query)
{
vector<int> queryfarm;
sort(query.begin(), query.end(), [](int x, int y){
return idx[x].back() > idx[y].back(); });
for(auto x: query)
add(queryfarm, idx[x].back());
return verify(queryfarm);
}
int main()
{
scanf("%d%d", &N, &Q);
for(int i=0; i<MAXN; ++i){
arr[i + MAXN] = N + 10;
L[i+MAXN] = R[i+MAXN] = i;
}
for(int i=0; i<N; ++i)
{
scanf("%d", arr+i+MAXN);
idx[arr[i+MAXN]].push_back(i+MAXN);
}
for(int i=MAXN-1; i>=1; --i)
{
L[i] = L[2*i]; R[i] = R[2*i+1];
arr[i] = min(arr[2*i], arr[2*i+1]);
idx[arr[i]].push_back(i);
}
for(int j=0; j<Q; ++j)
{
int T; scanf("%d", &T);
vector<int> a(T);
for(int i=0; i<T; ++i) scanf("%d", &a[i]);
pair<int, int> res = solve(a);
if(res.first == -1) puts("-1");
else printf("%d %d\n", res.first+1, res.second+1);
}
return 0;
}
Compilation message
easy.cpp: In function 'int main()':
easy.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
easy.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", arr+i+MAXN);
~~~~~^~~~~~~~~~~~~~~~~~
easy.cpp:90:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int T; scanf("%d", &T);
~~~~~^~~~~~~~~~
easy.cpp:92:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<T; ++i) scanf("%d", &a[i]);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7152 KB |
Correct |
| 2 |
Correct |
10 ms |
7168 KB |
Correct |
| 3 |
Incorrect |
8 ms |
7268 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
7152 KB |
Correct |
| 2 |
Correct |
10 ms |
7168 KB |
Correct |
| 3 |
Incorrect |
8 ms |
7268 KB |
Wrong |
| 4 |
Halted |
0 ms |
0 KB |
- |
