Submission #73239

#	Time	Username	Problem	Language	Result	Execution time	Memory
73239		test	Easy Data Structure Problem (FXCUP3_easy)	C++14	0 / 100	2 ms	356 KiB

easy

#include<bits/stdc++.h>
using namespace std;

const int MN = 100010;

int N, Q;
int A[MN], inva[MN];

vector<int> mrg(vector<int> &a, vector<int> &b) {
    vector<int> ret;
    int pos1 = 0, pos2 = 0;
    while(pos1 < a.size() && pos2 < b.size()) {
        if(a[pos1] < b[pos2]) ret.push_back(a[pos1++]);
        else ret.push_back(b[pos2++]);
    }
    while(pos1 < a.size()) ret.push_back(a[pos1++]);
    while(pos2 < b.size()) ret.push_back(b[pos2++]);
    return ret;
}

struct BIT {
    vector<int> tree;
    void init() {
        tree = vector<int>(4 * N, 0);
        build(0, N - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = A[l];
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = min(tree[2*n], tree[2*n + 1]);
    }
    vector<int> lquer(int idx, int l, int r, int n) {
        if(idx < l || r < idx) return vector<int>();
        vector<int> ret;
        if(tree[n] == A[idx]) ret.push_back(l);
        if(l == r) return ret;
        int m = (l + r)>>1;
        vector<int> L = lquer(idx, l, m, 2*n);
        vector<int> R = lquer(idx, m + 1, r, 2*n + 1);
        ret = mrg(ret, L);
        ret = mrg(ret, R);
        return ret;
    }
    vector<int> rquer(int idx, int l, int r, int n) {
        if(idx < l || r < idx) return vector<int>();
        vector<int> ret;
        if(tree[n] == A[idx]) ret.push_back(r);
        if(l == r) return ret;
        int m = (l + r)>>1;
        vector<int> L = rquer(idx, l, m, 2*n);
        vector<int> R = rquer(idx, m + 1, r, 2*n + 1);
        ret = mrg(ret, L);
        ret = mrg(ret, R);
        return ret;
    }
    vector<int> quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return vector<int>();
        if(a <= l && r <= b) return vector<int>(1, tree[n]);
        int m = (l + r)>>1;
        vector<int> L = quer(a, b, l, m, 2*n);
        vector<int> R = quer(a, b, m + 1, r, 2*n + 1);
        return mrg(L, R);
    }
} bit;

bool same(vector<int> &a, vector<int> b) {
    if(a.size() != b.size()) return false;
    for(int i = 0; i < a.size(); i++) if(a[i] != b[i]) return false;
    return true;
}

int main() {
    scanf("%d %d", &N, &Q);

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
    }
    for(int i = 0; i < N; i++) inva[A[i]] = i;

    bit.init();
    for(int i = 0; i < Q; i++) {
        int c; scanf("%d", &c);

        vector<int> X(c);
        int l = 1e9;
        int r = -1e9;
        for(int j = 0; j < c; j++) {
            scanf("%d", &X[j]);
            l = min(l, inva[ X[j] ]);
            r = max(r, inva[ X[j] ]);
        }

        vector<int> L = bit.lquer(l, 0, N - 1, 1);
        vector<int> R = bit.rquer(r, 0, N - 1, 1);

        int p = -1;
        int q = -1;
        for(int j = 0; j < L.size(); j++) {
            for(int k = 0; k < R.size(); k++) {
                if(same(X, bit.quer(L[j], R[k], 0, N - 1, 1))) {
                    p = L[j];
                    q = R[k];
                    break;
                }
            }
        }
        if(p == -1) printf("-1\n");
        else printf("%d %d\n", p + 1, q + 1);
    }
}

Compilation message (stderr)

easy.cpp: In function 'std::vector<int> mrg(std::vector<int>&, std::vector<int>&)':
easy.cpp:12:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size()) {
           ~~~~~^~~~~~~~~~
easy.cpp:12:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
easy.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size()) ret.push_back(a[pos1++]);
           ~~~~~^~~~~~~~~~
easy.cpp:17:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos2 < b.size()) ret.push_back(b[pos2++]);
           ~~~~~^~~~~~~~~~
easy.cpp: In function 'bool same(std::vector<int>&, std::vector<int>)':
easy.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < a.size(); i++) if(a[i] != b[i]) return false;
                    ~~^~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:103:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < L.size(); j++) {
                        ~~^~~~~~~~~~
easy.cpp:104:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = 0; k < R.size(); k++) {
                            ~~^~~~~~~~~~
easy.cpp:78: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:81:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &A[i]);
         ~~~~~^~~~~~~~~~~~~
easy.cpp:87:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int c; scanf("%d", &c);
                ~~~~~^~~~~~~~~~
easy.cpp:93:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &X[j]);
             ~~~~~^~~~~~~~~~~~~

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