Submission #72086

#	Time	Username	Problem	Language	Result	Execution time	Memory
72086		IDxTree (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	3 ms	356 KiB

easy

#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]; });
    for (int i = 1; i < c; ++i) {
        if ((rev[qs[i - 1]] + sz) == ((rev[qs[i]] + sz) ^ 1)) return pii(-1, -1);
    }
    
    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)

easy.cpp: In function 'pii calc()':
easy.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
     ~~~~~^~~~~~~~~~
easy.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:98: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:100:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", arr + i);
         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 33
• Subtask 2: 0 / 67