# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
72067 | IDxTree (#118) | Easy Data Structure Problem (FXCUP3_easy) | C++17 | 3 ms | 484 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;
int n;
int arr[100001];
int rev[100001];
int sz = 1;
int idx[1 << 18];
int st[1 << 18];
int ed[1 << 18];
int hi[1 << 18];
int contain(int x, int y) {
return st[x] <= st[y] && ed[y] <= ed[x];
}
pii calc() {
vector<int> qs;
int c;
scanf("%d", &c);
for (int i = 0; i < c; ++i) {
int x;
scanf("%d", &x);
qs.push_back(x);
}
sort(qs.begin(), qs.end(), [&](int i, int j) { return rev[i] < rev[j]; });
vector<int> nd(qs.size());
for (int i = 0; i < c; ++i) {
int tp = rev[qs[i]] + sz;
while (tp > 1) {
int nxt = tp >> 1;
if (idx[nxt] != idx[tp]) break;
if (i && contain(nxt, rev[qs[i - 1]] + sz)) break;
if (i + 1 < c && contain(nxt, rev[qs[i + 1]] + sz)) break;
tp = nxt;
}
nd[i] = tp;
for (int j = i; j--; ) {
int x = rev[qs[j]] + sz;
while (x > 1) {
int nxt = x >> 1;
if (idx[nxt] != idx[x]) break;
if (hi[nd[j + 1]] < hi[nxt]) break;
if (nd[j + 1] == (nxt ^ 1)) break;
if (j && contain(nxt, rev[qs[j - 1]] + sz)) break;
x = nxt;
}
nd[j] = x;
}
for (int j = i + 1; j < c; ++j) {
int x = rev[qs[j]] + sz;
while (x > 1) {
int nxt = x >> 1;
if (idx[nxt] != idx[x]) break;
if (hi[nd[j - 1]] < hi[nxt]) break;
if (nd[j - 1] == (nxt ^ 1)) break;
if (j + 1 < c && contain(nxt, rev[qs[j + 1]] + sz)) break;
x = nxt;
}
nd[j] = x;
}
int suc = 1;
for (int j = 1; j < c; ++j) {
if (ed[nd[j - 1]] + 1 != st[nd[j]]) {
suc = 0;
break;
}
}
if (suc) return pii(st[nd[0]], ed[nd.back()]);
}
return pii(-1, -1);
}
int main() {
int q;
scanf("%d%d", &n, &q);
for (int i = 0; i < n; ++i) {
scanf("%d", arr + i);
rev[arr[i]] = i;
}
while (sz < n) sz <<= 1;
for (int i = 0; i < n; ++i) idx[i + sz] = arr[i];
for (int i = n; i < sz; ++i) idx[i + sz] = n + 1;
for (int i = sz; --i; ) idx[i] = min(idx[i << 1], idx[i << 1 | 1]);
for (int i = 0; i < sz; ++i) st[i + sz] = ed[i + sz] = i;
for (int i = sz; --i; ) {
st[i] = st[i << 1];
ed[i] = ed[i << 1 | 1];
hi[i] = hi[i << 1] + 1;
}
for (int i = 0; i < q; ++i) {
int x, y;
tie(x, y) = calc();
if (x != -1) printf("%d %d\n", x + 1, y + 1);
else printf("-1\n");
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |