maximalseq.cc

/*
 * Can we really implement anything, no matter how inefficient, and have it pass
 * just because it's frigging C++???
 */
#include <bits/stdc++.h>
using namespace std;

class Node {
    int start, end;
    set<int> rset;
    Node *left, *right;
public:
    Node(vector<int> &nums) : Node(0, nums.size()-1, nums) { }
    Node(int start, int end, vector<int> & nums) : start(start), end(end) {
        if (start == end)
            rset = set<int>(nums.begin()+start, nums.begin()+start+1);
        else {
            int half = (start + end)/2;
            left = new Node(start, half, nums);
            right = new Node(half+1, end, nums);
            set_union(left->rset.begin(), left->rset.end(), 
                      right->rset.begin(), right->rset.end(), 
                      inserter(rset, rset.begin()));
        }
    }

    set<int> query(int frm, int to) {
        set<int> result;
        if (start > to || end < frm)
            return result;
        if (frm <= start && end <= to)
            return rset;
        else {
            auto lset = left->query(frm, to);
            auto rset = right->query(frm, to);
            set_union(lset.begin(), lset.end(), 
                      rset.begin(), rset.end(), 
                      inserter(result, result.begin()));
            return result;
        }
    }
};

int
main()
{
    int n;
    cin >> n;
    vector<int> nums;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        nums.push_back(x);
    }

    Node * root = new Node(nums);
    int q;
    cin >> q;
    for (int k = 0; k < q; k++) {
        int i, m;
        cin >> i >> m;
        set<int> numzz;
        for (int j = 0; j < m; j++) {
            int x;
            cin >> x;
            numzz.insert(x);
        }

        auto isok = [root, numzz](int lo, int mid) -> bool {
            set<int> rq = root->query(lo, mid);
            return includes(numzz.begin(), numzz.end(), rq.begin(), rq.end());
        };
        int lo = i - 1;
        int hi = n;
        int count = 0;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (isok(lo, mid)) {
                count += 1 + mid - lo;
                lo = mid + 1;
            } else
                hi = mid;
        }

        cout << count << endl;
    }
}