Submission #72158

#	Time	Username	Problem	Language	Result	Execution time	Memory
72158		IDxTree (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	100 / 100	139 ms	13672 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];
}

int check(const vector<int> &qs, int s, int e) {
    s += sz; e += sz;
    vector<int> ans;
    while (s <= e) {
        if ((s & 1) == 1) ans.push_back(idx[s++]);
        if ((e & 1) == 0) ans.push_back(idx[e--]);
        s >>= 1; e >>= 1;
    }
    sort(ans.begin(), ans.end(), [&](int i, int j) { return rev[i] < rev[j]; });
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    if (qs.size() != ans.size()) return 0;
    for (int i = 0; i < qs.size(); ++i) {
        if (qs[i] != ans[i]) return 0;
    }
    return 1;
}

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(c);
    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 s = st[nd[0]], e = ed[nd[c - 1]];
        if (check(qs, s, e)) return pii(s, e);
    }
    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 = 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 'int check(const std::vector<int>&, int, int)':
easy.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qs.size(); ++i) {
                     ~~^~~~~~~~~~~
easy.cpp: In function 'pii calc()':
easy.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
     ~~~~~^~~~~~~~~~
easy.cpp:57: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:107: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:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", arr + i);
         ~~~~~^~~~~~~~~~~~~~~

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